Speaker: Dan Cranston, Virginia Commonwealth University
Date and time: Tuesday, March 6, 1-2pm
Place: Rome 771
Title: Coloring Squares of Planar Graphs
Abstract: The square, , of a graph is formed from by adding an edge joining each pair of vertices at distance 2 in . If has maximum degree , then can have maximum degree as big as and the chromatic number, , of can be as big as . Two examples that achieve equality are the 5-cycle and the Petersen graph. In general these bounds cannot be improved much. For example, if is the incidence graph of a projective plane and has maximum degree , then has maximum degree and . However, for planar graphs, we can do much better.
It is easy to show that if is a planar graph with maximum degree , then ; in fact, this bound can be greatly improved. However, constructions show that we cannot improve it beyond . Further, every graph with maximum degree trivially satisfies . We survey various classes of planar graphs for which this trivial lower bound holds with equality or nearly holds with equality. More precisely, we seek a graph class and a constant such that every graph with maximum degree satisfies . Our main result is that if is defined by forbidding certain lengths of cycles, then has this property if and only if we forbid either (i) 4-cycles or (ii) all even cycles of length at least 6.
This is joint work with Ilkyoo Choi.