Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Negative results on ...
Conference paper

Negative results on acyclic improper colorings

Pascal Ochem ORCID (1)
(1) Laboratoire Bordelais de Recherche en Informatique
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3441
License
https://about.hal.science/hal-authorisation-v1
Indicators
623
Views
616
Downloads

Negative results on acyclic improper colorings

Pascal Ochem ORCID (1)
(1) Laboratoire Bordelais de Recherche en Informatique
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
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • $\mathrm{NP}$-completeness
  • acyclic colorings
  • oriented colorings
Cited by

Source: OpenCitations

  • Acyclic colorings of graph subdivisions revisited

    Journal of Discrete Algorithms

    Authors : Debajyoti Mondal ORCID, Rahnuma Islam Nishat ORCID, Sue Whitesides, Md. Saidur Rahman ORCID

    Journal reference : Volume 16, 2012, pp. 90-103

    DOI : 10.1016/j.jda.2012.06.001

  • Acyclic Coloring with Few Division Vertices

    Lecture notes in computer science

    Authors : Debajyoti Mondal ORCID, Rahnuma Islam Nishat ORCID, Md. Saidur Rahman ORCID, Sue Whitesides

    Journal reference : Volume , 2012, pp. 86-99

    DOI : 10.1007/978-3-642-35926-2_11

  • An Oriented 6-Coloring of Planar Graphs with Girth at Least 9

    Graphs and Combinatorics

    Authors : T. H. Marshall

    Journal reference : Volume 32, 2015, pp. 1101-1116

    DOI : 10.1007/s00373-015-1612-8

  • On the oriented chromatic index of oriented graphs

    Journal of Graph Theory

    Authors : Pascal Ochem ORCID, Alexandre Pinlou ORCID, Éric Sopena ORCID

    Journal reference : Volume 57, 2007, pp. 313-332

    DOI : 10.1002/jgt.20286

  • Acyclic 3-coloring of generalized Petersen graphs

    Journal of Combinatorial Optimization

    Authors : Enqiang Zhu ORCID, Zepeng Li ORCID, Zehui Shao ORCID, Jin Xu ORCID, Chanjuan Liu ORCID

    Journal reference : Volume 31, 2014, pp. 902-911

    DOI : 10.1007/s10878-014-9799-9

  • On Chromatic Number of Colored Mixed Graphs

    Lecture notes in computer science

    Authors : Sandip Das ORCID, Soumen Nandi ORCID, Sagnik Sen

    Journal reference : Volume , 2017, pp. 130-140

    DOI : 10.1007/978-3-319-53007-9_12

  • Homomorphisms and colourings of oriented graphs: An updated survey

    Discrete Mathematics

    Authors : É. Sopena ORCID

    Journal reference : Volume 339, 2015, pp. 1993-2005

    DOI : 10.1016/j.disc.2015.03.018

  • Graph Coloring

    Undergraduate topics in computer science

    Authors : Md. Saidur Rahman ORCID

    Journal reference : Volume , 2017, pp. 91-102

    DOI : 10.1007/978-3-319-49475-3_7

  • Acyclic Choosability of Graphs with Small Maximum Degree

    Lecture notes in computer science

    Authors : Daniel Gonçalves ORCID, Mickaël Montassier

    Journal reference : Volume , 2005, pp. 239-248

    DOI : 10.1007/11604686_21

  • Acyclic Colorings of Graph Subdivisions

    Lecture notes in computer science

    Authors : Debajyoti Mondal ORCID, Rahnuma Islam Nishat ORCID, Sue Whitesides, Md. Saidur Rahman ORCID

    Journal reference : Volume , 2011, pp. 247-260

    DOI : 10.1007/978-3-642-25011-8_20
Preview
Loading PDF preview...