Daniel Cranston's Slides

Disclaimer: These slides were not designed to be viewed without my narration. Thus, they are likely at points to be ambiguous.
Nonetheless, they do provide an overview of the topics covered. If you want more details, check out the corresponding papers on arXiv or on the page of my writing.

Expository

• A Survey of k-critical Graphs
  
  A graph G is k-critical if G has chromatic number k, but every subgraph of G has chromatic number less than k. This is a survey talk on k-critical graphs for a workshop at the American Institute of Mathematics (in Pasadena, CA) in October 2024.


• Edge-coloring Multigraphs
  
  This is a 2017 survey talk on edge-coloring both simple graphs and multigraphs (that also mentions a few recent results of Landon Rabern and me). For simple graphs we focus on classes where chromatic index equals maximum degree. For multigraphs, we study a powerful recoloring tool, Tashkinov trees.


• No More Moore Graphs
  
  This is an expository talk, proving the famous result of Hoffman and Singleton that Moore graphs exist only for degrees 2, 3, 7, and (possibly) 57.


• A proof of Bertrand's Postulate
  
  This result states that for every positive integer n, there exists a prime p such that n < p ≤ 2n. This is an expository talk I gave at Davidson, showcasing a beautiful proof due to Erdos. Our presentation follows that in "Proofs from the Book".


• An Introduction to Nowhere-zero Flows
  
  For a planar graph, a nowhere-zero flow is equivalent to a face-coloring. However, such flows are also defined for non-planar graphs. In other words, nowhere-zero flows generalize the notion of face-coloring to non-planar graphs.


• Euler's Pentagonal Number Theorem
  
  This result gives an explicit value for each coefficient in the expansion of the infinite product Π_k≥1(1-x^k). We present a pretty bijective proof using integer partitions.

Research

• Rosenfeld Counting: Proper Conflict-free Coloring of Graphs with Large Maximum Degree
  
  A proper conflict-free coloring is a proper coloring such that each non-isolated vertex has a color that is used exactly once on its (open) neighborhood. We prove that every graph has such a coloring from a list assignment L whenever |L(v)| ≥ 1.656Δ when Δ, the maximum degree, is big enough. This talk doubles as an introduction to Rosenfeld counting, which is similar to the Lovasz Local Lemma, but often requires fewer technical details.
  
  
• Cliques in Squares of Graphs with Maximum Average Degree less than 4
  
  We show that if a graph G has maximum average degree less than 4 and maximum degree at most D, then G² has clique number at most 5D/2+532. In the special case that G is 2-degenerate, this bound improves to 5D/2+72. This is best possible up to the additive constant, due to a construction that achieves the lower bound 5D/2.
  
  
• Optimally Reconfiguring List Colorings Given Large Lists
  
  Let L be a list-assignment with |L(v)| ≥ d(v) + 2 for all vertices v of a graph G. Cambie, Cames van Batenburg, and I conjectured that every L-coloring of G can be reconfigured into every other L-coloring (at each step, recoloring a single vertex and maintaining a proper L-coloring) using at most n(G) + μ(G) steps. (Here n(G) is the order of G and μ(G) is its matching number.) In these slides, we survey related results and prove two weaker forms of the conjecture.
  
  
• In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent
  
  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). Here we show that for most 6-regular toroidal graphs (of which there are infinitely many) all 5-colorings are Kempe equivalent.
  
  
• Kempe Equivalent List Colorings
  
  (k-Kempe equivalence is defined in the previous paragraph.) 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 K₂☐K₃, 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 K₂☐K₃). 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 L_H all L_H-colorings are L_H-equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment L_G for G all L_G-colorings are L_G-equivalent.
  
  
• Using the Potential Method to Color Near-bipartite Graphs
  
  A graph is near-bipartite if we can partition its vertex set into sets I and F so that I is an independent set and F induces a forest. All 2-colorable graphs are near-bipartite and all near-bipartite graphs are 3-colorable, and each containment is proper. Determining if a graph is near-bipartite is NP-hard (not surprisingly). We give a sufficient condition for a graph to be near-bipartite, and it is sharp infinitely often.
  
  
• Vertex Partitions into an Independent Set and a Forest with Each Component Small
  
  This work refines the result in the previous paragraph. We want to partition V(G) into sets I and F_k so that I is an independent set and F induces a forest with each tree of order at most k. We call this an (I,F_k) partition. For each integer k ≥ 2, we determine a sharp bound on mad(G) such that V(G) has an (I,F_k) partition. For each k we construct an infinite family of examples showing our result is best possible.
  
  
• Circular Coloring of Planar Graphs
  
  We study sufficient conditions for a planar graph with large girth to have a homomorphism to an odd cycle. This problem generalizes Grotzsch's Theorem that all triangle-free planar graphs are 3-colorable. Here we show that (if G is planar, then) girth at least 10 implies a homomorphism to C₅ and girth at least 16 implies a homomorphism to C₇.
  
  
• Bootstrap Percolation Thresholds in Plane Tilings using Regular Polygons
  
  Bootstrap Percolation models the spread of disease. If a face is healthy, but has k infected neighbors, then the face becomes infected. For a plane graph G, we randomly infect some of the faces (each independently, with probability p), and ask for the probability that eventually all faces become infected. The percolation threshold is the largest k such that this probability is at least 1/2. We find the thresholds for many tilings of the plane by regular polygons, including for all Archimedean lattices.
  
  
• Coloring Squares of Planar Graphs of Girth 5
  
  This paper answers affirmatively a 2008 conjecture of Dvorak, Kral, Nejedly, Skrekovski that, for some constant D, for every planar graph G with girth at least 5 and maximum degree at least D, the chromatic number of the square of G is at most D+2. (They had proved the same for girth 6.) We prove their conjecture in the more general setting of online list coloring.
  
  
• Fractional Coloring of Planar Graphs and the Plane
  
  This an invited talk that I gave at the 24^th Workshop on Cycles and Colourings, in Slovakia. It begins with a brief survey of fractional coloring, sketches the proof that planar graphs are 9/2-colorable (see below), then outlines a proof for a new lower bound on the fractional chromatic number of the plane (here we are coloring all points of the plane and two points get disjoint color sets if they are at distance exactly 1 in the plane). I gave a related talk at VCU that just presents the lower bound for fractionally coloring the plane.
  
  
• Planar graphs are 9/2-colorable and have big independent sets (Here's another version for a more expert audience.)
  
  The 4 Color Theorem says that every planar graph has a proper coloring with 4 colors. But the proof relies heavily on computers. The 5 Color Theorem is analogous (but weaker), although it has a simple proof. Here we prove something in between: a 9/2 Color Theorem, which does not need computers for the proof.
  
  
• Regular Graphs of Odd Degree are Antimagic
  
  A labeling of a graph G is a bijection from its edges to the integers 1,2,...,|E(G)|. The sum at a vertex (given a labeling) is the sum of labels on edges incident to that vertex. A labeling is antimagic if all of these sums are distinct. We prove that every regular graph of odd degree (at least 3) has an antimagic labeling.
  
  
• Painting Squares with Δ²-1 colors
  Here we consider the problem of (online) list-coloring the square of a graph G with maximum degree Δ. We prove that Δ²-1 colors suffice, except for the obvious case when G² has a clique of size at least Δ².
  
  
• Boundedness of Positive Solutions of the Reciprocal Max-Type Difference Equation x_n=max_1<i<t(Aⁱ_n-1/x_n-i) with Periodic Parameters
  This is a departure from what I normally do. It's joint work with Candace Kent, my colleague at VCU. The proofs use epsilons, deltas, and a bit of elementary number theory (but no graphs).
  
  
• Borodin and Kostochka conjectured that if G has maximum degree Δ ≥ 9 and no clique of size Δ, then the chromatic number of G is at most Δ-1. We prove partial results on this conjecture. (The three talks below are independent.)
    talk 1: Graphs with χ=Δ have big cliques and the West Fest version
    talk 2: Coloring a claw-free graph with Δ-1 colors
    talk 3: Conjectures equivalent to the Borodin-Kostochka Conjecture: Coloring a graph with Δ-1 colors
  
  
• Revolutionaries and Spies
  
  We study a game on a graph G played by r revolutionaries and s spies. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a neighboring vertex or not move, and then each spy has the same option. The revolutionaries win if m of them meet at some vertex having no spy (at the end of a round); the spies win if they can avoid this forever. We provide conditions for the spies to win on various classes of graphs.
  
  
• Overlap Number of Graphs
  
  An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. We prove upper bounds on the size of the base set needed for such a representation of all n-vertex graphs in various families such as trees, planar graphs, bipartite graphs, and all graphs.
  
  
• List colorings of K₅-minor-free graphs with special list assignments
  
  Let G be a graph with no K₅-minor. We consider list-assignments L such that |L(v)| ≥ min{d(v),k} for some integer k, and determine conditions under which G always has an L-coloring from such a list-assignment L.
  
  
• Crossings, Colorings, and Cliques
  
  Albertson conjectured that if a graph G has chromatic number k, then its crossing number (minimum number of edge crossings in a plane drawing of G) is at least the crossing number of K_k. Previously, this was known for all k ≤ 6. Here we extend it to all k ≤ 12.
  
  
• (7,2)-edge-choosability of Some 3-regular Graphs
  
  In a 3-regular graph, a list-assignment L gives to each edge e a set L(e) of 7 available colors. We consider sufficient conditions under which we can choose a set of 2 colors for each edge e from L(e) such that any two edges with a common endpoint choose disjoint sets of colors.
  
  
• Star Coloring Planar Graphs with High Girth
  
  A star coloring is a proper coloring in which each pair of colors induces a star forest (each component has at most one vertex with degree more than 1). We prove that every planar graph with girth at least 13 has a star coloring that uses at most 4 colors.
  
  
• Injective Coloring
  
  An injective coloring of a graph gives distinct colors to each pair of vertices with a common neighbor. The maximum average degree of graph G, denoted mad(G), is the largest average degree of all its subgraphs. Let G be a graph with maximum degree 3. We show that G has an injective coloring (a) with 5 colors if mad(G) < 36/13 and (b) with 4 colors if mad(G) < 5/2.
  
  
• Discharging and Reducibility: An Introduction by Example
  
  This talk contains some content from the Star Coloring talk above, but has more background, and is aimed at a wider audience.
  
  
• List-coloring the Square of a Subcubic Graph
    talk 1: General bounds
          We show that G² has list-chromatic number at most 8, unless G contains the Petersen graph (the square of which is K₁₀).
    talk 2: Planar graphs with high girth
          When G is planar with girth at least 7 (resp. 9), the upper bound above can be improved (resp. improved even more).
  
  
• Antimagic labelings of regular bipartite graphs
  
  A labeling of a graph G assigns the integers 1,...,|E(G)| bijectively to the edges of G. The sum at a vertex v is the sum of the labels on edges incident to v. A labeling is antimagic if the sums at all vertices are distinct. We prove that every regular bipartite graph (with degree at least 2) has a labeling that is antimagic.
  
  
• Edge-choosability of planar graph with no kites
  
  A kite is formed from K₄ by removing an edge. Let G be a planar graph with no kites and with Δ ≥ 6. We show that G has an L-edge-coloring whenever |L(e)| = Δ + 1 for all e in G.