Negative results on acyclic improper colorings

Abstract : Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number $k$ is at most $k2^{k-1}$. We prove that this bound is tight for $k \geq 3$. We also show that some improper and/or acyclic colorings are $\mathrm{NP}$-complete on a class $\mathcal{C}$ of planar graphs. We try to get the most restrictive conditions on the class $\mathcal{C}$, such as having large girth and small maximum degree. In particular, we obtain the $\mathrm{NP}$-completeness of $3$-$\mathrm{ACYCLIC \space COLORABILITY}$ on bipartite planar graphs with maximum degree $4$, and of $4$-$\mathrm{ACYCLIC \space COLORABILITY}$ on bipartite planar graphs with maximum degree $8$.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184430
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:58:30 PM
Last modification on : Thursday, January 11, 2018 - 6:20:17 AM
Long-term archiving on : Sunday, November 15, 2015 - 11:10:17 AM

File

dmAE0169.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184430, version 1

Collections

Citation

Pascal Ochem. Negative results on acyclic improper colorings. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.357-362. ⟨hal-01184430⟩

Share

Metrics

Record views

150

Files downloads

401