Chromatic Graph Theory
Responsable et prÃ©sident:
Joan P. Hutchinson (Macalester College, emerita)
[
PDF]
 JOAN HUTCHINSON, Macalester College, emerita
A variation on Heawoodlistcoloring for graphs on surfaces [PDF]

Thomassen's celebrated planar 5listcoloring theorem shows that if the vertices of a plane graph have $k$lists except that the vertices on one face have only $(k2)$lists, then the graph can be listcolored when $k = 5$. That result is not true for graphs on nonplanar surfaces, but we prove a related result for graphs on surfaces with $k$ equal to the Heawood number of the surface.
 GARY MACGILLIVRAY, University of Victoria
Locally injective homomorphisms [PDF] [SLIDES]

A homomorphism $f$ of a graph $G$ to a graph $H$ is \emph{locally injective} if, for every vertex $x$, the restriction of $f$ to the neighbourhood of $x$ is injective. When $G$ and $H$ are directed graphs there are a number of ways that the term ``neighbourhood'' could be interpreted. We shall survey results about the complexity of locally injective homomorphisms and their associated locally injective colourings, and briefly mention some recent work with Russell Campbell and Nancy Clarke.
 LUKE POSTLE, Emory University
Linear Isoperimetric Bounds in Graph Coloring [PDF]

A family of graphs on surfaces is hyperbolic if the number of vertices inside every planar disk is linear in the size of its boundary, and strongly hyperbolic if the same is true for every annulus.
We prove that $6$listcritical graphs (and $4$listcritical graphs of girth at least five) are strongly hyperbolic. Applying our structure theorem for strongly hyperbolic families shows that: the number of such graphs on a fixed surface is finite and so provides a lineartime algorithm for testing $5$choosability; locally planar graphs with distant precolored vertices are $5$choosable; a $5$listcolorable graph has exponentially many $5$listcolorings.
 STAN WAGON, Macalester College
Computational Hamiltonianism [PDF]

Several sophisticated algorithms (blossom for matching, integerlinear programming, traveling salesman) are now easily available. This leads to algorithms to:
1. find a minimal vertex coloring of a graph;
2. find a minimal edge coloring of a graph;
3. find a Hamiltonian decomposition for regular graphs;
4. determine if a graph is Hamiltonconnected;
5. find a perfect 1factorization for graphs.
I have applied these ideas to all 7183 graphs in \emph {Mathematica}'s database, resolving a very high percentage of them (all 7183 for problems 2, 3, and 4) regarding these five problems. Such computations lead to some intriguing conjectures.