Parameterized complexity of vertex colouring (Q1811065)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parameterized complexity of vertex colouring |
scientific article |
Statements
Parameterized complexity of vertex colouring (English)
0 references
10 June 2003
0 references
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.
0 references
vertex coloring
0 references
fixed-parameter problem
0 references
parameterized complexity
0 references
split graph
0 references
bipartite graph
0 references
0 references