Daniel Cranston's Writing


I work in discrete mathematics, mainly in structural graph theory and graph coloring.
You can find my publications indexed on Google Scholar, zbMATH, and dblp. My papers are nearly all available on arXiv. But below I highlight a few that I think are particularly worth your time. You might also be interested in slides for some of my talks.


Book

  • Graph Coloring Methods (2024)

    This is the book that I wish that someone had given me when I was in grad school, around the time that I was starting to prove original results. But no one did, because it hadn't been written. Each chapter studies a single method, and presents numerous examples applying that method, generally in order of increasing difficulty. The book is designed to be suitable for a topics course in graph coloring, as well as self-study. Download it for free, or read more here.

Survey Articles

  • Coloring, List Coloring, and Painting Squares of Graphs (and other related problems) (Electronic J. Combinatorics, 2023)

    We survey work on coloring, list coloring, and painting squares of graphs; in particular, we consider strong edge-coloring. We focus primarily on planar graphs and other sparse classes of graphs. (This was published as a "Dynamic Survey" in the Electronic Journal of Combinatorics. So the idea is that it can be easily updated to reflect further work in the area. The most recent version was published in 2023.)

  • An Introduction to the Discharging Method via Graph Coloring (with Douglas West; Discrete Mathematics, 2017)

    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.

  • Brooks' Theorem and Beyond (with Landon Rabern; Journal of Graph Theory, 2015)

    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 analogues 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.


Selected Research Articles

  • Vertex Partitions into an Independent Set and a Forest with Each Component Small (with Matt Yancey; SIAM J. Discrete Math, 2021) slides

    I've written a few papers using the potential method, and this is probably my favorite. This technique is a way to "turbo charge" a discharging proof. We get more from our induction hypothesis, which allows us to prove stronger results about reducible configurations. As a consequence, results proved using the potential method are more often sharp (than results proved using discharging, but not using the potential method).

    For each integer k ≥ 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 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.

  • Acyclic edge-coloring of planar graphs: Δ colors suffice when Δ is large (SIAM J. Discrete Math, 2019)  slides

    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, χ'a(G), is the smallest number of colors allowing an acyclic edge-coloring of G. Clearly χ'a(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 χ'a(G) = Δ(G). We prove this conjecture.

  • Planar graphs are 9/2-colorable (with Landon Rabern; J. Combinatorial Theory, B, 2018) slides

    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.

  • Graphs with χ = Δ have big cliques (with Landon Rabern; SIAM J. Discrete Math, 2015) slides

    Brooks' Theorem states that if a graph has Δ ≥ 3 and ω ≤ Δ, then χ ≤ Δ. Borodin and Kostochka conjectured that if Δ ≥ 9 and ω ≤ Δ-1, then χ ≤ Δ-1. We show that if Δ ≥ 13 and ω ≤ Δ-4, then χ ≤Δ-1. For a graph G, let H denote the subgraph of G induced by vertices of degree Δ. We also show that if ω ≤ Δ-1 and ω(H) ≤ Δ-6, then χ ≤ Δ-1.

  • Kempe Equivalent List Colorings (with Reem Mahmoud; Combinatorica, 2024) slides

    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 K2☐K3, 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. We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again with a single exception K2☐K3). When k ≥ 4, the proof is completely self-contained, so implies 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 LH all LH-colorings are LH-equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment LG for G all LG-colorings are LG-equivalent.

  • Planar Graphs of Girth at least Five are Square (Δ+2)-Choosable (with Marthe Bonamy and Luke Postle; J. Combinatorial Theory, B, 2019) slides

    We prove a conjecture of Dvořák, Král, Nejedlý, and Škrekovski that planar graphs of girth at least five 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.