The complexity of changing colourings with bounded maximum degree
From MaRDI portal
Publication:407523
DOI10.1016/j.ipl.2010.05.026zbMath1234.68140OpenAlexW2074631242MaRDI QIDQ407523
Publication date: 27 March 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.05.026
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Precoloring extension. I: Interval graphs
- Some simplified NP-complete graph problems
- The four-colour theorem
- Local nature of Brooks' colouring for degree 3 graphs
- A note on graph coloring extensions and list-colorings
- A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
- Two-Processor Scheduling with Start-Times and Deadlines
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Precoloring Extension III: Classes of Perfect Graphs
- Colouring graphs when the number of colours is nearly the maximum degree
- Precoloring Extensions of Brooks' Theorem
- Unnamed Item
- Unnamed Item