### 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