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]

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]

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph K n. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G , we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of K n. [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]

For each integer k \geq 2, we determine a sharp bound on mad(G) such that V (G) can be partitioned into sets I and Fk, where I is an independent set and G[Fk] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is the best possible. Our results imply that every planar graph G of girth at least 9 (resp., 8, 7) has a partition of V (G) into an independent set I and a set F such that G[F] is a forest with each component of order at most 3 (resp., 4, 6). Hendrey, Norin, and Wood asked for the largest function g(a, b) such that if mad(G) < g(a, b), then V (G) has a partition into sets A and B such that mad(G[A]) < a and mad(G[B]) < b. They specifically asked for the value of g(1, b), i.e., the case when A is an independent set. Previously, the only values known were g(1, 4/3) and g(1, 2). We find g(1, b) whenever 4/3 < b < 2. [ABSTRACT FROM AUTHOR]

We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that if G is such a graph, then G2 is (Δ(G) + 72)-degenerate. This implies an upper bound of Δ(G) ∣ 73 on the chromatic number of G2 as well as on several variants of the chromatic number such as the list-chromatic number, paint number, Alon-Tarsi number, and correspondence chromatic number. We also show that if Δ(G) is sufficiently large, then the upper bounds on each of these parameters of G2 can all be lowered to Δ(G) + 2 (which is best possible). To complement these results, we show that 4-cycles are unique in having this property. Specifically, let S be a finite list of positive integers, with 4 ∉ S. For each constant C, we construct a planar graph Gs,c with no cycle with length in S, but for which χ(GS,C2) >Δ(Gs,c) + C. [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]

For a list assignment L and an L -coloring φ , a Kempe swap in φ is L-valid if it yields another L -coloring. Two L -colorings are L-equivalent if we can form one from another by a sequence of L -valid Kempe swaps. And a graph G is L-swappable if every two of its L -colorings are L -equivalent. We consider L -swappability of line graphs of planar graphs with large maximum degree. Let G be a planar graph with Δ (G) ≥ 9 and let H be the line graph of G. If L is a (Δ (G) + 1) -assignment to H , then H is L -swappable. Let G be a planar graph with Δ (G) ≥ 15 and let H be the line graph of G. If L is a Δ (G) -assignment to H , then H is L -swappable. The first result is analogous to one for L -choosability by Borodin, which was later strengthened by Bonamy. The second result is analogous to another for L -choosability by Borodin, which was later strengthened by Borodin, Kostochka, and Woodall. [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]

Abstract We show that every planar graph G has a 2-fold 9-coloring. In particular, this implies that G has fractional chromatic number at most 9 2. This is the first proof (independent of the 4 Color Theorem) that there exists a constant k < 5 such that every planar G has fractional chromatic number at most k. [ABSTRACT FROM AUTHOR]

Let G be a planar graph without 4-cycles and 5-cycles and with maximum degree [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]

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]

Abstract: We determine the list chromatic number of the square of a graph in terms of its maximum degree when its maximum average degree, denoted , is sufficiently small. For , if , then . In particular, if is planar with girth , then . Under the same conditions, , where is the list injective chromatic number. [Copyright &y& Elsevier]