The complexity of some acyclic improper colourings

DOI10.1016/J.DISC.2011.01.023zbMath1222.05046OpenAlexW2068626799MaRDI QIDQ533784

Elżbieta Sidorowicz, Katarzyna Jesse-Józefczyk, Mieczysław Borowiecki

Publication date: 6 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.01.023

zbMATH Keywords

graph algorithmssubcubic graphsacyclic colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Acyclic colorings of graphs with bounded degree ⋮ Acyclic improper colouring of graphs with maximum degree 4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic colorings of graphs with bounded degree
• Acyclic colorings of subcubic graphs
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• The complexity of satisfiability problems
• Acyclic colorings of planar graphs

This page was built for publication: The complexity of some acyclic improper colourings