Bibliographies thématiques / Properly colored subgraph / Articles de revues

Articles de revues sur le sujet « Properly colored subgraph »

Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Properly colored subgraph.
Auteur : Grafiati
Publié le 25 mai 2024

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les 25 meilleurs articles de revues pour votre recherche sur le sujet « Properly colored subgraph ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Parcourez les articles de revues sur diverses disciplines et organisez correctement votre bibliographie.

1

M, Jerlin Seles, et Dr U. Mary. « Strategy on Disaster Recovery Management based on Graph Theory Concepts ». International Journal of Recent Technology and Engineering (IJRTE) 10, no 4 (30 novembre 2021) : 31–34. http://dx.doi.org/10.35940/ijrte.d6535.1110421.

Texte intégral
Résumé :
The COVID-19 pandemic has asserted major baseline facts from disaster anthropology during the last three decades. Resilience could be based on the solution to the question: "What is the maximum amount of destruction, if any, that the graph (a network) can sustain while ensuring that at least one of each technology type remains and that the remaining induced subgraph is properly colored?" The concept of a graph's Chromatic Core Subgraph is a solution to the stated problem. In this paper, the pandemic graphs and certain sequential graphs are developed. For these graphs, the Chromatic core subgraph is obtained. The results of the pandemic graphs' Chromatic core subgraph are used to develop a disaster recovery strategy for the COVID-19 pandemic.
Styles APA, Harvard, Vancouver, ISO, etc.
2

Axenovich, Maria, Tao Jiang et Z. Tuza. « Local Anti-Ramsey Numbers of Graphs ». Combinatorics, Probability and Computing 12, no 5-6 (novembre 2003) : 495–511. http://dx.doi.org/10.1017/s0963548303005868.

Texte intégral
Résumé :
A subgraph H in an edge-colouring is properly coloured if incident edges of H are assigned different colours, and H is rainbow if no two edges of H are assigned the same colour. We study properly coloured subgraphs and rainbow subgraphs forced in edge-colourings of complete graphs in which each vertex is incident to a large number of colours.
Styles APA, Harvard, Vancouver, ISO, etc.
3

KOSTOCHKA, ALEXANDR, et MATTHEW YANCEY. « Large Rainbow Matchings in Edge-Coloured Graphs ». Combinatorics, Probability and Computing 21, no 1-2 (2 février 2012) : 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Texte intégral
Résumé :
Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly edge-colouredK4has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.
Styles APA, Harvard, Vancouver, ISO, etc.
4

Manoussakis, Y., M. Spyratos, Zs Tuza et M. Voigt. « Minimal colorings for properly colored subgraphs ». Graphs and Combinatorics 12, no 4 (décembre 1996) : 345–60. http://dx.doi.org/10.1007/bf01858468.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
5

Rödl, Vojtech, et Zsolt Tuza. « Rainbow subgraphs in properly edge-colored graphs ». Random Structures & ; Algorithms 3, no 2 (1992) : 175–82. http://dx.doi.org/10.1002/rsa.3240030207.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
6

Katić, Robert, Colton Magnant et Pouria Salehi Nowbandegani. « Forbidden Properly Edge-Colored Subgraphs that Force Large Highly Connected Monochromatic Subgraphs ». Graphs and Combinatorics 33, no 4 (26 mai 2017) : 969–79. http://dx.doi.org/10.1007/s00373-017-1804-5.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
7

Alon, Noga, Tao Jiang, Zevi Miller et Dan Pritikin. « Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints ». Random Structures and Algorithms 23, no 4 (11 novembre 2003) : 409–33. http://dx.doi.org/10.1002/rsa.10102.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
8

Jaradat, M. M. M., M. S. A. Bataineh et S. M. E. Radaideh. « Ramsey Numbers for Theta Graphs ». International Journal of Combinatorics 2011 (15 juin 2011) : 1–9. http://dx.doi.org/10.1155/2011/649687.

Texte intégral
Résumé :
The graph Ramsey number is the smallest integer with the property that any complete graph of at least vertices whose edges are colored with two colors (say, red and blue) contains either a subgraph isomorphic to all of whose edges are red or a subgraph isomorphic to all of whose edges are blue. In this paper, we consider the Ramsey numbers for theta graphs. We determine , for . More specifically, we establish that for . Furthermore, we determine for . In fact, we establish that if is even, if is odd.
Styles APA, Harvard, Vancouver, ISO, etc.
9

Markström, Klas, Andrew Thomason et Peter Wagner. « Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree ». Graphs and Combinatorics 27, no 2 (1 septembre 2010) : 243–49. http://dx.doi.org/10.1007/s00373-010-0970-5.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
10

Magnant, Colton, Daniel M. Martin et Pouria Salehi Nowbandegani. « Monochromatic Subgraphs in the Absence of a Properly Colored 4-Cycle ». Graphs and Combinatorics 34, no 6 (8 octobre 2018) : 1147–58. http://dx.doi.org/10.1007/s00373-018-1955-z.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
11

Alon, Noga, Alexey Pokrovskiy et Benny Sudakov. « Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles ». Israel Journal of Mathematics 222, no 1 (octobre 2017) : 317–31. http://dx.doi.org/10.1007/s11856-017-1592-x.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
12

JOUVE, FLORENT, et JEAN-SÉBASTIEN SERENI. « EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES ». Journal of the Australian Mathematical Society 105, no 1 (11 janvier 2018) : 79–102. http://dx.doi.org/10.1017/s1446788717000234.

Texte intégral
Résumé :
We prove a general large-sieve statement in the context of random walks on subgraphs of a given graph. This can be seen as a generalization of previously known results where one performs a random walk on a group enjoying a strong spectral gap property. In such a context the point is to exhibit a strong uniform expansion property for a suitable family of Cayley graphs on quotients. In our combinatorial approach, this is replaced by a result of Alon–Roichman about expanding properties of random Cayley graphs. Applying the general setting we show, for instance, that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (nonempty) subsets summing to $0$, and that a random colouring of the edges of a complete graph contains a monochromatic triangle.
Styles APA, Harvard, Vancouver, ISO, etc.
13

Erzurumluoğlu, Aras, et C. A. Rodger. « On Evenly-Equitable, Balanced Edge-Colorings and Related Notions ». International Journal of Combinatorics 2015 (4 mars 2015) : 1–7. http://dx.doi.org/10.1155/2015/201427.

Texte intégral
Résumé :
A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.
Styles APA, Harvard, Vancouver, ISO, etc.
14

Yuster, Raphael. « Rainbow $H$-factors ». Electronic Journal of Combinatorics 13, no 1 (15 février 2006). http://dx.doi.org/10.37236/1039.

Texte intégral
Résumé :
An $H$-factor of a graph $G$ is a spanning subgraph of $G$ whose connected components are isomorphic to $H$. Given a properly edge-colored graph $G$, a rainbow $H$-subgraph of $G$ is an $H$-subgraph of $G$ whose edges have distinct colors. A rainbow $H$-factor is an $H$-factor whose components are rainbow $H$-subgraphs. The following result is proved. If $H$ is any fixed graph with $h$ vertices then every properly edge-colored graph with $hn$ vertices and minimum degree $(1-1/\chi(H))hn+o(n)$ has a rainbow $H$-factor.
Styles APA, Harvard, Vancouver, ISO, etc.
15

Coll, Vincent, Colton Magnant et Kathleen Ryan. « Structure of Colored Complete Graphs Free of Proper Cycles ». Electronic Journal of Combinatorics 19, no 4 (6 décembre 2012). http://dx.doi.org/10.37236/2304.

Texte intégral
Résumé :
For a fixed integer $m$, we consider edge colorings of complete graphs which contain no properly edge colored cycle $C_{m}$ as a subgraph. Within colorings free of these subgraphs, we establish global structure by bounding the number of colors that can induce a spanning and connected subgraph. In the case of smaller cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.
Styles APA, Harvard, Vancouver, ISO, etc.
16

Alishahi, Meysam. « Colorful Subhypergraphs in Uniform Hypergraphs ». Electronic Journal of Combinatorics 24, no 1 (3 février 2017). http://dx.doi.org/10.37236/6154.

Texte intégral
Résumé :
There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [Colourful theorems and indices of homomorphism complexes, The Electronic Journal of Combinatorics, 2014] and by Simonyi and Tardos [Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics, 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.
Styles APA, Harvard, Vancouver, ISO, etc.
17

Zhang, Xiaoyan, Zan-Bo Zhang, Hajo Broersma et Xuelian Wen. « On the complexity of edge-colored subgraph partitioning problems in network optimization ». Discrete Mathematics & ; Theoretical Computer Science Vol. 17 no. 3, Discrete Algorithms (1 juillet 2016). http://dx.doi.org/10.46298/dmtcs.2159.

Texte intégral
Résumé :
International audience Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, a subgraph $H$ is said to be <i>monochromatic</i> if all its edges have the same color, and called <i>multicolored</i> if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.
Styles APA, Harvard, Vancouver, ISO, etc.
18

Gourvès, Laurent, Adria Lyra, Carlos A. Martinhon et Jérôme Monnot. « On paths, trails and closed trails in edge-colored graphs ». Discrete Mathematics & ; Theoretical Computer Science Vol. 14 no. 2, Graph Theory (3 septembre 2012). http://dx.doi.org/10.46298/dmtcs.586.

Texte intégral
Résumé :
Graph Theory International audience In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G(c) is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.
Styles APA, Harvard, Vancouver, ISO, etc.
19

Gowers, Timothy, et Oliver Janzer. « Improved bounds for the Erdős-Rogers function ». Advances in Combinatorics, 28 février 2020. http://dx.doi.org/10.19086/aic.12048.

Texte intégral
Résumé :
[Ramsey's Theorem](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one of the most prominent results in graph theory. In its simplest form, it asserts that every sufficiently large two-edge-colored complete graph contains a large monochromatic complete subgraph. This theorem has been generalized to a plethora of statements asserting that every sufficiently large structure of a given kind contains a large "tame" substructure. The article concerns a closely related problem: for a structure with a given property, find a substructure possessing an even stronger property. For example, what is the largest $K_3$-free induced subgraph of an $n$-vertex $K_4$-free graph? The answer to this question is approximately $n^{1/2}$. The lower bound is easy. If a given graph has a vertex of degree at least $n^{1/2}$, then its neighbors induce a $K_3$-free subgraph with at least $n^{1/2}$ vertices. Otherwise, a greedy procedure yields an independent set of size almost $n^{1/2}$. The argument generalizes to $K_s$-free induced subgraphs of $K_{s+1}$-free graphs. Dudek, Retter and Rödl provided a construction showing that the exponent $1/2$ cannot be improved and asked whether the same is the case for $K_s$-free induced subgraphs of $K_{s+2}$-free graphs. The authors answer this question by providing a construction of $K_{s+2}$-free $n$-vertex graphs with no $K_s$-free induced subgraph with $n^{\alpha_s}$ vertices with $\alpha_s<1/2$ for every $s\ge 3$. Their arguments extend to the case of $K_t$-free graphs with no large $K_s$-free induced subgraph for $s+2\le t\le 2s-1$ and $s\ge 3$.
Styles APA, Harvard, Vancouver, ISO, etc.
20

Guo, Zhiwei, Christoph Brause, Maximilian Geißer et Ingo Schiermeyer. « Compatible Spanning Circuits and Forbidden Induced Subgraphs ». Graphs and Combinatorics 40, no 1 (19 janvier 2024). http://dx.doi.org/10.1007/s00373-023-02735-8.

Texte intégral
Résumé :
AbstractA compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively.
Styles APA, Harvard, Vancouver, ISO, etc.
21

Fang, Chunqiu, Ervin Győri et Jimeng Xiao. « On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs ». Graphs and Combinatorics, 15 juin 2021. http://dx.doi.org/10.1007/s00373-021-02351-4.

Texte intégral
Résumé :
AbstractLet $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) be the maximum number of colors in an edge-coloring of $$K_{n}$$ K n with no properly colored copy of G. For a family $${\mathcal {F}}$$ F of graphs, let $$\mathrm{ex}(n, {\mathcal {F}})$$ ex ( n , F ) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in $${\mathcal {F}}$$ F as subgraphs. In this paper, we show that $$\mathrm{pr}(K_{n}, G)-\mathrm{ex}(n, \mathcal {G'})=o(n^{2}), $$ pr ( K n , G ) - ex ( n , G ′ ) = o ( n 2 ) , where $$\mathcal {G'}=\{G-M: M \text { is a matching of }G\}$$ G ′ = { G - M : M is a matching of G } . Furthermore, we determine the value of $$\mathrm{pr}(K_{n}, P_{l})$$ pr ( K n , P l ) for sufficiently large n and the exact value of $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) , where G is $$C_{5}, C_{6}$$ C 5 , C 6 and $$K_{4}^{-}$$ K 4 - , respectively. Also, we give an upper bound and a lower bound of $$\mathrm{pr}(K_{n}, K_{2,3})$$ pr ( K n , K 2 , 3 ) .
Styles APA, Harvard, Vancouver, ISO, etc.
22

Barát, János, András Gyárfás et Géza Tóth. « Monochromatic spanning trees and matchings in ordered complete graphs ». Journal of Graph Theory, 15 novembre 2023. http://dx.doi.org/10.1002/jgt.23058.

Texte intégral
Résumé :
AbstractWe study two well‐known Ramsey‐type problems for (vertex‐)ordered complete graphs. Two independent edges in ordered graphs can be nested, crossing, or separated. Apart from two trivial cases, these relations define six types of subgraphs, depending on which one (or two) of these relations are forbidden. Our first target is to refine a remark by Erdős and Rado that every 2‐coloring of the edges of a complete graph contains a monochromatic spanning tree. We show that forbidding one relation we always have a monochromatic (nonnested, noncrossing, and nonseparated) spanning tree in a 2‐edge‐colored ordered complete graph. On the other hand, if two relations are forbidden, then it is possible that we have monochromatic (nested, separated, and crossing) subtrees of size only in a 2‐colored ordered complete graph on vertices. Some of these results relate to drawings of complete graphs. For instance, the existence of a monochromatic nonnested spanning tree in 2‐colorings of ordered complete graphs verifies a more general conjecture for twisted drawings. Our second subject is to refine the Ramsey number of matchings, that is, pairwise independent edges for ordered complete graphs. Cockayne and Lorimer proved that for given positive integers , is the smallest integer with the following property: every ‐coloring of the edges of a complete graph contains a monochromatic matching with edges. We conjecture that this result can be strengthened: ‐colored ordered complete graphs on vertices contain monochromatic nonnested and also nonseparated matchings with edges. We prove this conjecture for some special cases including the following. (i) Every ‐colored ordered complete graph on vertices contains a monochromatic nonnested matching of size two ( case). We prove it by showing that the chromatic number of the subgraph of the Kneser graph induced by the nonnested 2‐matchings in an ordered complete graph on vertices is ‐chromatic. (ii) Every 2‐colored ordered complete graph on vertices contains a monochromatic nonseparated matching of size ( case). This is the hypergraph analog of a result of Kaiser and Stehlík who proved that the Kneser graph induced by the nonseparated 2‐matchings in an ordered complete graph on vertices is ‐chromatic.For nested, separated, and crossing matchings the situation is different. The smallest ensuring a monochromatic matching of size in every ‐coloring is in the first two cases and one less in the third case.
Styles APA, Harvard, Vancouver, ISO, etc.
23

Janssen, Jeannette, Rogers Mathew et Deepak Rajendraprasad. « Partial List Colouring of Certain Graphs ». Electronic Journal of Combinatorics 22, no 3 (20 septembre 2015). http://dx.doi.org/10.37236/4283.

Texte intégral
Résumé :
The partial list colouring conjecture due to Albertson, Grossman, and Haas (2000) states that for every $s$-choosable graph $G$ and every assignment of lists of size $t$, $1 \leq t \leq s$, to the vertices of $G$ there is an induced subgraph of $G$ on at least $\frac{t|V(G)|}{s}$ vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with chromatic number at least $\frac{|V(G)|-1}{2}$, chordless graphs, and series-parallel graphs.
Styles APA, Harvard, Vancouver, ISO, etc.
24

Assadi, Sepehr, Pankaj Kumar et Parth Mittal. « Brooks' Theorem in Graph Streams : A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring ». TheoretiCS Phase 2 (25 août 2023). http://dx.doi.org/10.46298/theoretics.23.9.

Texte intégral
Résumé :
Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed, the celebrated \Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with $\Delta$ colors. Can we find a $\Delta$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not $\Delta$-colorable or outputs a $\Delta$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for $\Delta$-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in $o(n^2)$ time -- we prove that neither of these tasks is possible for $\Delta$-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to $\Delta$-coloring. We then build on these insights to design a semi-streaming algorithm that uses $(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input -- the ones that form the basis of our impossibility results -- and $(ii)$ a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
Styles APA, Harvard, Vancouver, ISO, etc.
25

Cranston, Daniel W., et Landon Rabern. « Beyond Degree Choosability ». Electronic Journal of Combinatorics 24, no 3 (11 août 2017). http://dx.doi.org/10.37236/6179.

Texte intégral
Résumé :
Let $G$ be a connected graph with maximum degree $\Delta$. Brooks' theorem states that $G$ has a $\Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is degree-choosable if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a Gallai tree. This degree-choosability result was further strengthened to Alon—Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is degree-AT if $G$ has an Alon—Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon—Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.
Styles APA, Harvard, Vancouver, ISO, etc.
Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!

Vers la bibliographie