The complexity of changing colourings with bounded maximum degree

DOI10.1016/J.IPL.2010.05.026MaRDI QIDQ407523zbMATH OpenOpenAlexFDO

Authors 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 complexitygraph algorithmscombinatorial problems\(k\)-colouring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The complexity of \(H\)-colouring of bounded degree graphs
• Bounded Max-colorings of Graphs
• Bounded max-colorings of graphs
• The complexity of some graph colouring problems
• Reconfiguring colorings of graphs with bounded maximum average degree
• Complexity of coloring reconfiguration under recolorability constraints
• Degree‐bounded coloring of graphs: Variations on a theme by brooks
• On the Complexity of the Max-Edge-Coloring Problem with Its Variants
• The complexity of nonrepetitive coloring
• The complexity of generalized graph colorings

Cites work

• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
• A note on graph coloring extensions and list-colorings
• Colouring graphs when the number of colours is nearly the maximum degree
• Local nature of Brooks' colouring for degree 3 graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring Extensions of Brooks' Theorem
• Precoloring extension. I: Interval graphs
• Some simplified NP-complete graph problems
• The four-colour theorem
• Two-Processor Scheduling with Start-Times and Deadlines
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(4)

• Vertex Coloring of Comparability+ke and –ke Graphs
• The complexity of multicolouring
• scientific article; zbMATH DE number 1189240 (Why is no real title available?)
• Colouring graphs when the number of colours is almost the maximum degree

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

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