Pascal Ochem - Negative results on acyclic improper colorings

dmtcs:3441 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3441
Negative results on acyclic improper colorings

Authors: Pascal Ochem ORCID-iD1

  • 1 Laboratoire Bordelais de Recherche en Informatique

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$.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: $\mathrm{NP}$-completeness,acyclic colorings,oriented colorings,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1508.07217
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1508.07217
  • 1508.07217
  • 10.48550/arxiv.1508.07217
On homomorphism of oriented graphs with respect to push operation

7 Documents citing this article

Consultation statistics

This page has been seen 147 times.
This article's PDF has been downloaded 289 times.