CMS/SMC
CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
       

Chromatic Graph Theory
Organizer and Chair: Joan P. Hutchinson (Macalester College, emerita)
[PDF]

JOAN HUTCHINSON, Macalester College, emerita
A variation on Heawood-list-coloring for graphs on surfaces  [PDF]

Thomassen's celebrated planar 5-list-coloring theorem shows that if the vertices of a plane graph have $k$-lists except that the vertices on one face have only $(k-2)$-lists, then the graph can be list-colored 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$-list-critical graphs (and $4$-list-critical 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 linear-time algorithm for testing $5$-choosability; locally planar graphs with distant precolored vertices are $5$-choosable; a $5$-list-colorable graph has exponentially many $5$-list-colorings.

STAN WAGON, Macalester College
Computational Hamiltonianism  [PDF]

Several sophisticated algorithms (blossom for matching, integer-linear 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 Hamilton-connected;

5. find a perfect 1-factorization 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.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland