The complexity of some acyclic improper colourings

DOI10.1016/J.DISC.2011.01.023MaRDI QIDQ533784zbMATHOpenAlexFDO

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

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

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

Recommendations

• scientific article; zbMATH DE number 1341902
• Acyclic improper colourings of graphs with bounded maximum degree
• Acrylic improper colorings of graphs
• Acyclic improper choosability of subcubic graphs

Cites work

• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1341902 (Why is no real title available?)
• Acyclic colorings of planar graphs
• Acyclic colorings of subcubic graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• The complexity of satisfiability problems

Cited in

(5)

• Acyclic improper colouring of graphs with maximum degree 4
• Towards a version of Ohba's conjecture for improper colorings
• Improper colourings inspired by Hadwiger's conjecture
• Acrylic improper colorings of graphs
• scientific article; zbMATH DE number 1341902 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533784)