CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Chromatic Numbers of Graphs
Org: Joan Hutchinson (Macalester College)

KAREN L. COLLINS, Wesleyan University, Middletown CT 06459-0128
Bounds on the distinguishing chromatic number of a graph  [PDF]

Albertson and Collins defined the distinguishing number of graph $G$ as the minimum number of colors needed to color the vertices of $G$ so that only the trivial automorphism preserves the colors. Collins and Trenk defined the distinguishing chromatic number, $\chi_D(G)$, to be the minimum number of colors needed for a labeling which is both proper and distinguishing. We will generalize the classic Nordhaus-Gaddum theorem for $\chi(G)$ to $\chi_D(G)$ and discuss other bounds on $\chi_D(G)$.

JOHN GIMBEL, University of Alaska
Defective chromatic and cochromatic numbers  [PDF]

A set of vertices is k-sparse if it induces a graph with maximum degree at most k. Similarly, a set of vertices is k-dense if the compliment of the graph it induces has maximum degree at most k. We discuss minimum partitions of the vertex set into parts that are k-sparse (the k-defective chromatic number) and partitions where each part is k-sparse or k-dense (the k-defective cochromatic number).

RUTH HAAS, Smith College
The Canonical Coloring Graph  [PDF]

Given a graph $G$, a Canonical Coloring Graph $Can(G)$ has vertex set the set of all nonisomorphic colorings of the $G$, where the representative of each set of isomorphic colorings is chosen according to a canonical ordering. There is an edge between two colorings if they are identical on $V(G-x)$ for some $x\in V (G)$. $Can(G)$ depends on the choice of canonical representatives. In this talk we give recent results about properties of $Can(G)$.

JOAN HUTCHINSON, Macalester College
List-coloring extension results for planar graphs, Part I  [PDF]

M.O. Albertson has asked whether, given a planar graph $G$ with lists of size at least 5 for each vertex, there is a $d > 0$ such that whenever $P \subset V(G)$ has distance between every pair of vertices of $P$ at least $d$, then every precoloring of $P$ extends to a 5-list-coloring of $G$. With M. Axenovich and M.A. Lastrina we present results giving instances when the question has an affirmative answer.

MICHELLE LASTRINA, Iowa State University
List-coloring extension results for planar graphs, Part II  [PDF]

J.P. Hutchinson conjectured that, given a planar graph $G$ with two nonadjacent vertices on the unbounded face having lists of size 2, the remaining vertices on the unbounded face having lists of size 3 and all other vertices of $G$ having lists of size 5, then $G$ can be list-colored. Hutchinson proved the result for outerplanar graphs. With M. Axenovich we present various other types of graphs for which the conjecture holds.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria