Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184430
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:58:30 PM
Last modification on : Saturday, June 25, 2022 - 10:35:51 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:10:17 AM

File

dmAE0169.pdf
Publisher files allowed on an open archive

Identifiers

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, ⟨10.46298/dmtcs.3441⟩. ⟨hal-01184430⟩

Share

Metrics

Record views

87

Files downloads

438