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
- Euler's Pentagonal Number Theorem
This result gives an
explicit value for each coefficient in the expansion of the infinite
product Πk≥1(1-xk). We present a pretty bijective proof
using integer partitions.
Using the Potential Method to Color
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 Fk 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,Fk) partition.
For each integer k ≥ 2, we determine a sharp bound on mad(G) such that V(G)
has an (I,Fk) partition.
For each k we construct an infinite family of examples showing our result is
Circular Coloring of 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.
Regular Graphs of Odd Degree are
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
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.