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]

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]

Wegner conjectured that if G is a planar graph with maximum degree Δ ≥ 8 , then χ (G 2) ≤ 3 2 Δ + 1. This problem has received much attention, but remains open for all Δ ≥ 8. Here we prove an analogous bound on ω (G 2) : If G is a plane graph with Δ (G) ≥ 36 , then ω (G 2) ≤ ⌊ 3 2 Δ (G) ⌋ + 1. In fact, this is a corollary of the following lemma, which is our main result. If G is a plane graph with Δ (G) ≥ 19 and S is a maximal clique in G 2 with | S | ≥ Δ (G) + 20 , then there exist x , y , z ∈ V (G) such that S = { w : | N [ w ] ∩ { x , y , z } | ≥ 2 }. [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]

For integers a geq 2b > 0, a circular a/b-flow is a flow that takes values from { pm b,pm (b+ 1), . . . ,pm (a b)} . The Planar Circular Flow Conjecture states that every 2k-edge-connected planar graph admits a circular (2 + 2 k)-flow. The cases k = 1 and k = 2 are equivalent to the Four Color Theorem and Grotzschs 3-Color Theorem. For k geq 3, the conjecture remains open. Here we make progress when k = 4 and k = 6. We prove that (i) every 10-edge-connected planar graph admits a circular 5/2-flow and (ii) every 16-edge-connected planar graph admits a circular 7/3- flow. The dual version of statement (i) on circular coloring was previously proved by Dvov rak and Postle [Combinatorica, 37 (2017), pp. 863--886], but our proof has the advantages of being much shorter and avoiding the use of computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because the counterexamples to Jaegers original Circular Flow Conjecture are 12-edge-connected nonplanar graphs that admit no circular 7/3-flow. Thus, the planarity hypothesis of (ii) is essential. [ABSTRACT FROM AUTHOR]

A graph G is (a,b)‐choosable if given any list assignment L with ∣L(v)∣=a for each v∈V(G) there exists a function φ such that φ(v)⊆L(v) and ∣φ(v)∣=b for all v∈V(G), and whenever vertices x and y are adjacent φ(x)∩φ(y)=∅. Meng, Puleo, and Zhu conjectured a characterization of (4,2)‐choosable graphs. We prove their conjecture. [ABSTRACT FROM AUTHOR]

A simple graph G is overfull if jE(G)j > bjV (G)j=2c. By the pigeonhole principle, every overfull graph G has 0(G) > . The core of a graph, denoted G, is the subgraph induced by its vertices of degree . Vizing's adjacency lemma implies that if 0(G) >, then G contains cycles. Hilton and Zhao conjectured that if G is connected with 4 and G has maximum degree 2, then 0(G) > precisely when G is overfull. We prove this conjecture for the case = 4. [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]

Abstract We prove a conjecture of Dvořák, Král, Nejedlý, and Škrekovski that planar graphs of girth at least five with maximum degree Δ are square (Δ + 2)-colorable for large enough Δ. In fact, we prove the stronger statement that such graphs are square (Δ + 2)-choosable and even square (Δ + 2)-paintable. [ABSTRACT FROM AUTHOR]

Fix a graph G , a list-assignment L for G , and L -colorings α and β. An L -recoloring sequence, starting from α , recolors a single vertex at each step, so that each resulting intermediate coloring is a proper L -coloring. An L -recoloring sequence transforms α to β if its initial coloring is α and its final coloring is β. We prove there exists an L -recoloring sequence that transforms α to β and recolors each vertex at most a constant number of times if (i) G is triangle-free and planar and L is a 7-assignment, or (ii) mad (G) < 17 / 5 and L is a 6-assignment or (iii) mad (G) < 22 / 9 and L is a 4-assignment. Parts (i) and (ii) confirm conjectures of Dvořák and Feghali. [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]

An antimagic labeling of a graph G with m edges is a bijection from [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 reconfiguration graph C k (G) for the k -colourings of a graph G has a vertex for each proper k -colouring of G , and two vertices of C k (G) are adjacent precisely when those k -colourings differ on a single vertex of G. Much work has focused on bounding the maximum value of diam C k (G) over all n -vertex graphs G. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if L is a list-assignment for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C L (G) ≤ n (G) + μ (G). We also conjecture that if (L , H) is a correspondence cover for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C (L , H) (G) ≤ n (G) + τ (G). (Here μ (G) and τ (G) denote the matching number and vertex cover number of G.) For every graph G , we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda's Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) diam C L (G) ≤ n (G) + 2 μ (G) and diam C (L , H) (G) ≤ n (G) + 2 τ (G). Our second main result proves that both conjectured bounds hold, whenever all v satisfy | L (v) | ≥ 2 d (v) + 1. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree. The full paper can also be found at arxiv.org/abs/2204.07928. [ABSTRACT FROM AUTHOR]

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1,2,3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures for graphs with maximum average degree less than 8/3. The conjectures are already confirmed for larger families, but the structure theorems and reducibility results are of independent interest. [ABSTRACT FROM AUTHOR]