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 my papers page.

Expository

• Edge-coloring Multigraphs
  This is a 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 regular graphs of degree 2, 3, 7, or (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, presenting a beautiful proof due to Erdos.


• An Introduction to Nowhere-zero Flows
  For a planar graph, a nowhere-zero flow is equivalent to a face-coloring. However,
  they 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

• 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 works 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
  
  
• 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.
  (The three talks 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
  
  
• Overlap Number of Graphs
  
  
• List colorings of K₅-minor-free graphs with special list assignments
  
  
• Crossings, Colorings, and Cliques
  
  
• (7,2)-edge-choosability of Some 3-regular Graphs
  
  
• Star Coloring Planar Graphs with High Girth
  
  
• Injective Coloring
  
  
• 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
    talk 2: Planar graphs with high girth
  
  
• Antimagic labelings of regular bipartite graphs
  
  
• Edge-choosability of planar graph with no kites

Back to my homepage.