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
 Edgecoloring Multigraphs
This is a survey talk on edgecoloring 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 Nowherezero
Flows
For a planar graph, a nowherezero flow is equivalent to a
facecoloring. However,
they are also defined for nonplanar graphs. In other
words, nowherezero flows
generalize the notion of facecoloring to nonplanar
graphs.
 Euler's Pentagonal Number Theorem
This result gives an
explicit value for each coefficient in the expansion of the infinite
product Π_{k≥1}(1x^{k}). We present a pretty bijective proof
using integer partitions.
Research

Using the Potential Method to Color
Nearbipartite Graphs
A graph is nearbipartite 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 2colorable
graphs are nearbipartite and all nearbipartite graphs are 3colorable, and
each containment is proper. Determining if a graph is nearbipartite is
NPhard (not surprisingly). We give a sufficient condition for a graph to be
nearbipartite, 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/2colorable (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/2colorable 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 Δ^{2}1
colors
Here we consider the problem of (online) listcoloring the square of a graph
G with maximum degree Δ.
We prove that Δ^{2}1 colors
suffice, except for the obvious case when G^{2} has a clique of size at
least Δ^{2}.

Boundedness of Positive Solutions of the Reciprocal MaxType Difference Equation
x_{n}=max_{1<i<t}(A^{i}_{n}1/x_{ni})
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 clawfree graph
with Δ1 colors
talk 3: Conjectures equivalent to the
BorodinKostochka Conjecture: Coloring a graph with Δ1 colors
 Revolutionaries and Spies
 Overlap Number of Graphs
 List colorings of K_{5}minorfree
graphs with special list assignments
 Crossings, Colorings, and Cliques
 (7,2)edgechoosability of Some 3regular 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.
 Listcoloring the Square of a Subcubic Graph
talk 1: General bounds
talk 2: Planar graphs with high girth
 Antimagic labelings of regular bipartite graphs
 Edgechoosability of planar graph with no kites
Back to my homepage.