Acceder

Bibliografías temáticas / Properly colored subgraph / Artículos de revistas

Artículos de revistas sobre el tema "Properly colored subgraph"

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Properly colored subgraph.

Autor: Grafiati

Publicado: 25 de mayo de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 25 mejores artículos de revistas para su investigación sobre el tema "Properly colored subgraph".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

Axenovich, Maria, Tao Jiang y Z. Tuza. "Local Anti-Ramsey Numbers of Graphs". Combinatorics, Probability and Computing 12, n.º 5-6 (noviembre de 2003): 495–511. http://dx.doi.org/10.1017/s0963548303005868.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

KOSTOCHKA, ALEXANDR y MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs". Combinatorics, Probability and Computing 21, n.º 1-2 (2 de febrero de 2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

Manoussakis, Y., M. Spyratos, Zs Tuza y M. Voigt. "Minimal colorings for properly colored subgraphs". Graphs and Combinatorics 12, n.º 4 (diciembre de 1996): 345–60. http://dx.doi.org/10.1007/bf01858468.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

Alon, Noga, Tao Jiang, Zevi Miller y Dan Pritikin. "Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints". Random Structures and Algorithms 23, n.º 4 (11 de noviembre de 2003): 409–33. http://dx.doi.org/10.1002/rsa.10102.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

Markström, Klas, Andrew Thomason y Peter Wagner. "Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree". Graphs and Combinatorics 27, n.º 2 (1 de septiembre de 2010): 243–49. http://dx.doi.org/10.1007/s00373-010-0970-5.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Alon, Noga, Alexey Pokrovskiy y Benny Sudakov. "Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles". Israel Journal of Mathematics 222, n.º 1 (octubre de 2017): 317–31. http://dx.doi.org/10.1007/s11856-017-1592-x.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

JOUVE, FLORENT y JEAN-SÉBASTIEN SERENI. "EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES". Journal of the Australian Mathematical Society 105, n.º 1 (11 de enero de 2018): 79–102. http://dx.doi.org/10.1017/s1446788717000234.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

Yuster, Raphael. "Rainbow $H$-factors". Electronic Journal of Combinatorics 13, n.º 1 (15 de febrero de 2006). http://dx.doi.org/10.37236/1039.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Coll, Vincent, Colton Magnant y Kathleen Ryan. "Structure of Colored Complete Graphs Free of Proper Cycles". Electronic Journal of Combinatorics 19, n.º 4 (6 de diciembre de 2012). http://dx.doi.org/10.37236/2304.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Alishahi, Meysam. "Colorful Subhypergraphs in Uniform Hypergraphs". Electronic Journal of Combinatorics 24, n.º 1 (3 de febrero de 2017). http://dx.doi.org/10.37236/6154.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

Zhang, Xiaoyan, Zan-Bo Zhang, Hajo Broersma y 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 de julio de 2016). http://dx.doi.org/10.46298/dmtcs.2159.

Texto completo

Resumen

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$.

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

Gourvès, Laurent, Adria Lyra, Carlos A. Martinhon y 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 de septiembre de 2012). http://dx.doi.org/10.46298/dmtcs.586.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

Gowers, Timothy y Oliver Janzer. "Improved bounds for the Erdős-Rogers function". Advances in Combinatorics, 28 de febrero de 2020. http://dx.doi.org/10.19086/aic.12048.

Texto completo

Resumen

[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$.

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Guo, Zhiwei, Christoph Brause, Maximilian Geißer y Ingo Schiermeyer. "Compatible Spanning Circuits and Forbidden Induced Subgraphs". Graphs and Combinatorics 40, n.º 1 (19 de enero de 2024). http://dx.doi.org/10.1007/s00373-023-02735-8.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

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

Texto completo

Resumen

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 ) .

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

Janssen, Jeannette, Rogers Mathew y Deepak Rajendraprasad. "Partial List Colouring of Certain Graphs". Electronic Journal of Combinatorics 22, n.º 3 (20 de septiembre de 2015). http://dx.doi.org/10.37236/4283.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

Cranston, Daniel W. y Landon Rabern. "Beyond Degree Choosability". Electronic Journal of Combinatorics 24, n.º 3 (11 de agosto de 2017). http://dx.doi.org/10.37236/6179.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!