Parameterized complexity of vertex colouring
type: Item
instance of: scholarly article
title: Parameterized complexity of vertex colouring
zbMATH Open document ID: 1015.05027
DOI: 10.1016/S0166-218X(02)00242-1
author: Leizhen Cai
published in: Discrete Applied Mathematics
publication date: 2003-06-10T00:00:00Z
review text: This paper studies the complexity of the vertex coloring problem (assign as few as possible colors to the vertices of a given graph such that adjacent vertices have different colors), for families of graphs, obtained by adding or removing some fixed number \(k\) of vertices or edges to a known family of graphs. Several results are shown. In particular, it is shown that vertex coloring can be solved in linear time, when a fixed number \(k\) of edges is added or removed from a split graph, and that it can be solved in polynomial time, but it is hard for the complexity class \(W[1]\) (from Downey-Fellows parameterized complexity theory) for split graphs with \(k\) vertices added. It is linear time solvable when one vertex or two edges are added to a bipartite graph, but becomes NP-complete when two vertices or three edges are added to a bipartite graph.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1925248
zbMATH Keywords: vertex coloring
zbMATH Keywords: fixed-parameter problem
zbMATH Keywords: parameterized complexity
zbMATH Keywords: split graph
zbMATH Keywords: bipartite graph
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Easy problems for tree-decomposable graphs
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Scheduling with incompatible jobs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4503944
cites work: Q4193514
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Q3328583
cites work: The splittance of a graph
cites work: Q4368728
cites work: Q4368729
cites work: Generalized coloring for tree-like graphs
cites work: The NP-completeness column: an ongoing guide
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Q4940046
cites work: Q4869540
full work available at URL: s0166-218x(02)00242-1
OpenAlex ID: W2130673833
description: scientific article; zbMATH DE number 1925248