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.
- Edge-coloring Multigraphs
This is a survey talk on edge-coloring both simple graphs and multigraphs (that
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,
- No More Moore Graphs
This is an expository talk, proving the famous result of Hoffman and Singleton
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
For a planar graph, a nowhere-zero flow is equivalent to a
they are also defined for non-planar graphs. In other
words, nowhere-zero flows
generalize the notion of face-coloring to non-planar
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
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
This an invited talk that I gave at the 24th 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
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,
does not need computers for the proof.
Painting Squares with Δ2-1
Here we consider the problem of (online) list-coloring the square of a graph
G with maximum degree Δ.
We prove that Δ2-1 colors
suffice, except for the obvious case when G2 has a clique of size at
Boundedness of Positive Solutions of the Reciprocal Max-Type Difference Equation
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 Δ ≥
and no clique of size Δ, then the chromatic number of G is at most
(The three talks are independent.)
talk 1: Graphs with χ=Δ
have big cliques and the West Fest
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 K5-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.