The complexity of changing colourings with bounded maximum degree
type: Item
instance of: scholarly article
title: The complexity of changing colourings with bounded maximum degree
zbMATH Open document ID: 1234.68140
author: Tom Rackham
published in: Information Processing Letters
publication date: 2012-03-27T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6018468
zbMATH Keywords: combinatorial problems
zbMATH Keywords: computational complexity
zbMATH Keywords: graph algorithms
zbMATH Keywords: \(k\)-colouring
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.05.026
OpenAlex ID: W2074631242
cites work: Precoloring Extensions of Brooks' Theorem
cites work: A note on graph coloring extensions and list-colorings
cites work: Precoloring extension. I: Interval graphs
cites work: Q5782525
cites work: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
cites work: Two-Processor Scheduling with Start-Times and Deadlines
cites work: Some simplified NP-complete graph problems
cites work: Q4838466
cites work: Precoloring Extension III: Classes of Perfect Graphs
cites work: Colouring graphs when the number of colours is nearly the maximum degree
cites work: A note on \(K^-_{\Delta +1}\)-free precolouring with \(\Delta\) colours
cites work: The four-colour theorem
cites work: Local nature of Brooks' colouring for degree 3 graphs
DOI: 10.1016/J.IPL.2010.05.026
Recommended article: The complexity of \(H\)-colouring of bounded degree graphs
Recommended article: Bounded Max-colorings of Graphs
Recommended article: Bounded max-colorings of graphs
Recommended article: The complexity of some graph colouring problems
Recommended article: Reconfiguring colorings of graphs with bounded maximum average degree
Recommended article: Complexity of Coloring Reconfiguration under Recolorability Constraints
Recommended article: Degree‐bounded coloring of graphs: Variations on a theme by brooks
Recommended article: On the Complexity of the Max-Edge-Coloring Problem with Its Variants
Recommended article: The complexity of nonrepetitive coloring
Recommended article: The complexity of generalized graph colorings
description: scientific article; zbMATH DE number 6018468