The complexity of changing colourings with bounded maximum degree
From MaRDI portal
Publication:407523
DOI10.1016/j.ipl.2010.05.026zbMath1234.68140MaRDI 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
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- Unnamed Item
- 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