Search

The coloring reconfiguration graph Ck(G) ${{\mathscr{C}}}_{k}(G)$ has as its vertex set all the proper k $k$‐colorings of G $G$, and two vertices in Ck(G) ${{\mathscr{C}}}_{k}(G)$ are adjacent if their corresponding k $k$‐colorings differ on a single vertex. Cereceda conjectured that if an n $n$‐vertex graph G $G$ is d $d$‐degenerate and k≥d+2 $k\ge d+2$, then the diameter of Ck(G) ${{\mathscr{C}}}_{k}(G)$ is O(n2) $O({n}^{2})$. Bousquet and Heinrich proved that if G $G$ is planar and bipartite, then the diameter of C5(G) ${{\mathscr{C}}}_{5}(G)$ is O(n2) $O({n}^{2})$. (This proves Cereceda's Conjecture for every such graph with degeneracy 3.) They also highlighted the particular case of Cereceda's Conjecture when G $G$ is planar and has no 3‐cycles. As a partial solution to this problem, we show that the diameter of C5(G) ${{\mathscr{C}}}_{5}(G)$ is O(n2) $O({n}^{2})$ for every planar graph G $G$ with no 3‐cycles and no 5‐cycles. [ABSTRACT FROM AUTHOR]

An α , β -Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors α and β . Two k-colorings of a graph are k-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than k colors). Las Vergnas and Meyniel showed that if a graph is (k - 1) -degenerate, then each pair of its k-colorings are k-Kempe equivalent. Mohar conjectured the same conclusion for connected k-regular graphs. This was proved for k = 3 by Feghali, Johnson, and Paulusma (with a single exception K 2 □ K 3 , also called the 3-prism) and for k ≥ 4 by Bonamy, Bousquet, Feghali, and Johnson. In this paper we prove an analogous result for list-coloring. For a list-assignment L and an L-coloring φ , a Kempe swap is called L-valid for φ if performing the Kempe swap yields another L-coloring. Two L-colorings are called L-equivalent if we can form one from the other by a sequence of L-valid Kempe swaps. Let G be a connected k-regular graph with k ≥ 3 and G ≠ K k + 1 . We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only K 2 □ K 3 ). Further, if G ∈ { K k + 1 , K 2 □ K 3 } , L is a Δ -assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When k ≥ 4 , the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let H be a graph such that for every degree-assignment L H all L H -colorings are L H -equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment L G for G all L G -colorings are L G -equivalent. [ABSTRACT FROM AUTHOR]

A coloring of a graph G is a map f : V (G) → Z + such that f (v) ≠ f (w) for all v w ∈ E (G). A coloring f is an odd-sum coloring if ∑ w ∈ N [ v ] f (w) is odd, for each vertex v ∈ V (G). The odd-sum chromatic number of a graph G , denoted χ os (G) , is the minimum number of colors used (that is, the minimum size of the range) in an odd-sum coloring of G. Caro, Petruševski, and Škrekovski showed, among other results, that χ os (G) is well-defined for every finite graph G and , in fact, χ os (G) ≤ 2 χ (G). Thus, χ os (G) ≤ 8 for every planar graph G (by the 4 Color Theorem), χ os (G) ≤ 6 for every triangle-free planar graph G (by Grötzsch's Theorem), and χ os (G) ≤ 4 for every bipartite graph. Caro et al. asked, for every even Δ ≥ 4 , whether there exists g Δ such that if G is planar with maximum degree Δ and girth at least g Δ then χ os (G) ≤ 5. They also asked, for every even Δ ≥ 4 , whether there exists g Δ such that if G is planar and bipartite with maximum degree Δ and girth at least g Δ then χ os (G) ≤ 3. We answer both questions negatively. We also refute a conjecture they made, resolve one further problem they posed, and make progress on another. [ABSTRACT FROM AUTHOR]

A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. This notion was recently introduced by Petruševski and Škrekovski, who proved that every planar graph admits an odd 9-coloring; they also conjectured that every planar graph admits an odd 5-coloring. Shortly after, this conjecture was confirmed for planar graphs of girth at least seven by Cranston; outerplanar graphs by Caro, Petruševski, and Škrekovski. Building on the work of Caro, Petruševski, and Škrekovski, Petr and Portier then further proved that every planar graph admits an odd 8-coloring. In this note we prove that every 1-planar graph admits an odd 23 -coloring, where a graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. [ABSTRACT FROM AUTHOR]

The Borodin–Kostochka Conjecture states that for a graph G $G$, if Δ(G)≥9 ${\rm{\Delta }}(G)\ge 9$ and ω(G)≤Δ(G)−1 $\omega (G)\le {\rm{\Delta }}(G)-1$, then χ(G)≤Δ(G)−1 $\chi (G)\le {\rm{\Delta }}(G)-1$. We prove the Borodin–Kostochka Conjecture for (P5,gem) $({P}_{5},\text{gem})$‐free graphs, that is, graphs with no induced P5 ${P}_{5}$ and no induced K1∨P4 ${K}_{1}\vee {P}_{4}$. [ABSTRACT FROM AUTHOR]

A strong edge-coloring φ of a graph G assigns colors to edges of G such that φ (e 1) ≠ φ (e 2) whenever e 1 and e 2 are at distance no more than 1. It is equivalent to a proper vertex coloring of the square of the line graph of G. In 1990 Faudree, Schelp, Gyárfás, and Tuza conjectured that if G is a bipartite graph with maximum degree 3 and sufficiently large girth, then G has a strong edge-coloring with at most 5 colors. In 2021 this conjecture was disproved by Lužar, Mačajová, Škoviera, and Soták. Here we give an alternative construction to disprove the conjecture. [ABSTRACT FROM AUTHOR]

An acyclic edge-coloring of a graph G is a proper edge-coloring of G such that the subgraph induced by any two color classes is acyclic. The acyclic chromatic index, &#967';α (G), is the smallest number of colors allowing an acyclic edge-coloring of G. Clearly &#967';α(G) ≥ Δ(G) for every graph G. Cohen, Havet, and Müller conjectured that there exists a constant M such that every planar graph with Δ(G) ≥ M has χ'α (G) = Δ(G). We prove this conjecture. [ABSTRACT FROM AUTHOR]

Let G be a planar graph without 4-cycles and 5-cycles and with maximum degree [ABSTRACT FROM AUTHOR]

Let Xℓ and XOL denote the list-chromatic number and online list-chromatic number. We prove that if G is a quasi-line graph with maximum degree greater than clique number, i.e., Δ(G) > ω(G), and Δ (G) ≥ 69, then its online list-chromatic number is less than its maximum degree, i.e., XOL(G) ≤ Δ(G) - 1. Together with our previous work, this implies that if G is a claw-free graph with Δ(G) > ω(G) and Δ(G) > 69, then its list-chromatic number is less than its maximum degree, i.e., Xℓ (G) ≤ Δ(G) - 1. This verifies the list-coloring analogue of a conjecture of Borodin and Kostochka for every claw-free graph G with Δ(G) ≥ 69. [ABSTRACT FROM AUTHOR]

We provide a “how-to” guide to the use and application of the Discharging Method. Our aim is not to exhaustively survey results proved by this technique, but rather to demystify the technique and facilitate its wider use, using applications in graph coloring as examples. Along the way, we present some new proofs and new problems. [ABSTRACT FROM AUTHOR]

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon-Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin-Kostochka Conjecture and Reed's Conjecture. [ABSTRACT FROM AUTHOR]

Brooks’ theorem implies that if a graph has Δ ≥ 3 and χ > Δ, then ω = Δ+1. Borodin and Kostochka conjectured that if Δ ≥ 9 and χ ≥ Δ, then ω ≥ Δ. We show that if Δ ≥ 13 and χ ≥ Δ, then ω ≥ Δ−3. For a graph G, let H(G) denote the subgraph of G induced by vertices of degree Δ. We also show that if χ ≥ Δ, then ω ≥ Δ or ω(H(G)) ≥ Δ − 5. [ABSTRACT FROM AUTHOR]

Borodin and Kostochka conjectured that every graph G with maximum degree Δ ≥ 9 satisfies χ ≤ max { ω , Δ − 1 } . We carry out an in-depth study of minimum counterexamples to the Borodin–Kostochka conjecture. Our main tool is the identification of graph joins that are f -choosable, where f ( v ) ≔ d ( v ) − 1 for each vertex v . Such a join cannot be an induced subgraph of a vertex critical graph with χ = Δ , so we have a wealth of structural information about minimum counterexamples to the Borodin–Kostochka conjecture. Our main result proves that certain conjectures that are prima facie weaker than the Borodin–Kostochka conjecture are in fact equivalent to it. One such equivalent conjecture is the following: Any graph with χ = Δ = 9 contains K 3 ∨ K 6 ¯ as a subgraph. [ABSTRACT FROM AUTHOR]

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d( v) the degree of vertex v, is G L-list colorable for every list assignment L with | L( v)| = min{ d( v), 6} for all v∈ V( G)? More generally, we ask for which pairs ( r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5-minor-free r-connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L-list colorable for every list assignment L with | L( v)| = min{ d( v), k} for all v∈ V( G)? We investigate this question by considering the components of G[ S k], where S k: = { v∈ V( G)| d( v)8 k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d( S k) in G between the components of G[ S k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18-30, 2012 [ABSTRACT FROM AUTHOR]

Abstract: Let denote the maximum average degree (over all subgraphs) of and let denote the injective chromatic number of . We prove that if , then ; and if , then . Suppose that is a planar graph with girth and . We prove that if , then ; similarly, if , then . [ABSTRACT FROM AUTHOR]

A graph is (7, 2)-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose 2 colors for each edge from its list so that no color is chosen for two incident edges. We show that every 3-edge-colorable graph is (7, 2)-edge-choosable and also that many non-3-edge-colorable 3-regular graphs are (7, 2)-edge-choosable. [ABSTRACT FROM AUTHOR]