DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Negative results on acyclic improper colorings

Pascal Ochem

Abstract


Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number k is at most k2k-1. We prove that this bound is tight for k≥3. We also show that some improper and/or acyclic colorings are NP-complete on a class C of planar graphs. We try to get the most restrictive conditions on the class C, such as having large girth and small maximum degree. In particular, we obtain the NP-completeness of 3-acyclic colorability on bipartite planar graphs with maximum degree 4, and of 4-acyclic colorability on bipartite planar graphs with maximum degree 8.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional