Title: List Coloring the Square of a Subcubic Graph
Speaker: Dan Cranston, University of Illinois
Date: Thursday, March 29, 2007 3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In a {list coloring} each vertex is assigned a list of k colors, then the graph is properly colored so that each vertex receives a color from its list. If a graph is list colorable for each assignment of lists of size k, the graph is {k-choosable}. We show that the square of a subcubic graph is 8-choosable. We also show that if G is a planar subcubic graph with girth at least 7, then G^2 is 7-choosable; and if G is a planar subcubic graph with girth at least 9, then G^2 is 6-choosable.
This is joint work with Seog-Jin Kim.