The complexity of some acyclic improper colourings

DOI10.1016/J.DISC.2011.01.023zbMATH Open1222.05046OpenAlexW2068626799MaRDI QIDQ533784FDOQ533784

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

Recommendations

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

zbMATH Keywords

graph algorithmssubcubic graphsacyclic colourings

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The complexity of satisfiability problems
• Acyclic colorings of planar graphs
• Title not available (Why is that?)
• Acyclic colourings of graphs with bounded degree
• Title not available (Why is that?)
• 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

Cited In (5)

• Towards a version of Ohba's conjecture for improper colorings
• Title not available (Why is that?)
• Acyclic colourings of graphs with bounded degree
• Improper colourings inspired by Hadwiger's conjecture
• Acyclic improper colouring of graphs with maximum degree 4

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)