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]

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.

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]

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]

A multigraph G is near-bipartite if V (G) can be partitioned as I, F such that I is an independent set and F induces a forest. We prove that a multigraph G is near-bipartite when 3|W| - 2|E(G[W])| ≥ 1 for every W ⊆ V (G), and G contains no K4 and no Moser spindle. We prove that a simple graph G is near-bipartite when 8|W| -5| E(G[W])| ≥ - 4 for every W ⊆ V (G), and G contains no subgraph from some finite family H. We also construct infinite families to show that both results are the best possible in a very sharp sense. [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]

We consider graphs G with [ABSTRACT FROM AUTHOR]

In 2011, the second author conjectured that every line graph G satisfies χ(G) ≤ max {ω(G), 5Δ(G)+8/6}. This conjecture is best possible as shown by replacing each edge in a 5-cycle by k parallel edges and taking the line graph. In this paper we prove the conjecture. We also develop more general techniques and results that will likely be of independent interest, due to their use in attacking the Goldberg-Seymour 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]

An antimagic labeling of a graph G with m edges is a bijection from [ABSTRACT FROM AUTHOR]

We prove that every claw-free graph G that does not contain a clique on Δ(G) ≥ 9 vertices can be Δ(G) -- 1 colored. [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]