Search

Hocquard, Kim, and Pierron constructed, for every even integer D≥2 $D\ge 2$, a 2‐degenerate graph GD ${G}_{D}$ with maximum degree D $D$ such that ω(GD2)=52D $\omega ({G}_{D}^{2})=\frac{5}{2}D$. We prove for (a) all 2‐degenerate graphs G $G$ and (b) all graphs G $G$ with mad(G)<4 $\text{mad}(G)\lt 4$, upper bounds on the clique number ω(G2) $\omega ({G}^{2})$ of G2 ${G}^{2}$ that match the lower bound given by this construction, up to small additive constants. We show that if G $G$ is 2‐degenerate with maximum degree D $D$, then ω(G2)≤52D+72 $\omega ({G}^{2})\le \frac{5}{2}D+72$ (with ω(G2)≤52D+60 $\omega ({G}^{2})\le \frac{5}{2}D+60$ when D $D$ is sufficiently large). And if G $G$ has mad(G)<4 $\text{mad}(G)\lt 4$ and maximum degree D $D$, then ω(G2)≤52D+532 $\omega ({G}^{2})\le \frac{5}{2}D+532$. Thus, the construction of Hocquard et al. is essentially the best possible. Our proofs introduce a “token passing” technique to derive crucial information about nonadjacencies in G $G$ of vertices that are adjacent in G2 ${G}^{2}$. This is a powerful technique for working with such graphs that has not previously appeared in the literature. [ABSTRACT FROM AUTHOR]

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]

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

An antimagic labeling of a graph G with m edges is a bijection from [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]