Parameterized complexity of vertex colouring (Q1811065)

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.