Ilkyoo Choi, Choosability of Toroidal Graphs with Forbidden Structures

Choosability of Toroidal Graphs with Forbidden Structures
2014/07/07 Monday 4PM-5PM
Room 1409
The choosability $$\chi_\ell(G)$$ of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that $$\chi_\ell(G)\leq 7$$, and $$\chi_\ell(G)=7$$ if and only if G contains $$K_7$$. Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and $$\chi_\ell(G)=6$$ if and only if G contains $$K_6$$. They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that $$\chi_\ell(G)=5$$ if and only if G contains $$K_5$$. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither $$K_5$$ nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither $$K^-_5$$ (a $$K_5$$ missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.

Tags: