Map-critical graphs on a fixed surface
by
Yared Nigussie
ETSU
Coauthors: Jaroslav Nesetril

The `H-coloring problem' is a generalization of the usual vertex coloring problem, which studies if any given graph G is homomorphic to H. Hence, the case H = K_k is the study of k-colorable graphs. A graph G is an obstruction to H-coloring if G is not homomorphic to H, but its every proper subgraph is. Hence, the widely known k-color-critical graphs are obstructions to K₍k-1)-coloring.

We prove that for every planar core graph H (except K₁ and K₄) there are infinitely many planar obstructions for H-coloring. For 5-colorable K₅-free toroidal graphs, we show a similar result. This obtains a converse to Thomassen theorem (for the case of toroidal 5-colorable graphs) that claims that there are only finitely many obstructions to K₅-coloring.

Date received: March 25, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-17.