Log in

Relevant bibliographies by topics / Properly colored subgraph / Journal articles

To see the other types of publications on this topic, follow the link: Properly colored subgraph.

Journal articles on the topic 'Properly colored subgraph'

Author: Grafiati

Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 25 journal articles for your research on the topic 'Properly colored subgraph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Rödl, Vojtech, and 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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

Zhang, Xiaoyan, Zan-Bo Zhang, Hajo Broersma, and 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 (July 1, 2016). http://dx.doi.org/10.46298/dmtcs.2159.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

24

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

25

Cranston, Daniel W., and Landon Rabern. "Beyond Degree Choosability." Electronic Journal of Combinatorics 24, no. 3 (August 11, 2017). http://dx.doi.org/10.37236/6179.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!