The complexity of changing colourings with bounded maximum degree

DOI10.1016/j.ipl.2010.05.026zbMath1234.68140OpenAlexW2074631242MaRDI QIDQ407523

Tom Rackham

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

zbMATH Keywords

computational complexitycombinatorial problemsgraph algorithms\(k\)-colouring

Mathematics Subject Classification ID

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

This page was built for publication: The complexity of changing colourings with bounded maximum degree