### DIMACS Special Seminar

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.