# 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$.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.357-362, 2005, DMTCS Proceedings
Domaine :

Littérature citée [14 références]

https://hal.inria.fr/hal-01184430
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:58:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:10:17

### Fichier

dmAE0169.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184430, version 1

### Citation

Pascal Ochem. Negative results on acyclic improper colorings. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.357-362, 2005, DMTCS Proceedings. 〈hal-01184430〉

### Métriques

Consultations de la notice

## 120

Téléchargements de fichiers