The complexity of changing colourings with bounded maximum degree

DOI10.1016/J.IPL.2010.05.026zbMATH Open1234.68140OpenAlexW2074631242MaRDI QIDQ407523FDOQ407523

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Precoloring extension. I: Interval graphs
• Title not available (Why is that?)
• Precoloring Extension III: Classes of Perfect Graphs
• 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
• Colouring graphs when the number of colours is nearly the maximum degree
• Precoloring Extensions of Brooks' Theorem

Cited In (2)

• The complexity of multicolouring
• Vertex Coloring of Comparability+ke and –ke Graphs

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)