Parameterized complexity of vertex colouring Original Research Article

For a family F of graphs and a nonnegative integer k, F+ke and F−ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F+kv denotes the family of graphs that can be made into F graphs by deleting at most k vertices. This paper is mainly concerned with the parameterized complexity of the vertex colouring problem on F+ke, F−ke and F+kv for various families F of graphs. In particular, it is shown that the vertex colouring problem is fixed-parameter tractable (linear time for each fixed k) for split+ke graphs and split−ke graphs, solvable in polynomial time for each fixed k but W[1]-hard for split+kv graphs. Furthermore, the problem is solvable in linear time for bipartite+1v graphs and bipartite+2e graphs but, surprisingly, NP-complete for bipartite+2v graphs and bipartite+3e graphs.