Colouring of graphs with Ramsey-type forbidden subgraphs

A colouring of a graph G = (V, E) is a mapping c: V -> {1,2, ... } such that c(u) not equal c(v) if uv is an element of E; if vertical bar c (V)vertical bar <= k then c is a k-colouring. The COLOURING problem is that of testing whether a given graph has a k-colouring for some given integer k. If a graph contains no induced subgraph isomorphic to any graph in some family H, then it is called H-free. The complexity of COLOURING for H-free graphs with vertical bar H vertical bar = 1 has been completely classified. When vertical bar H vertical bar = 2, the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs {H-1, H-2}, where we allow H-1 to have a single edge and H-2 to have a single non-edge. Instead of showing only polynomial-time solvability, we prove that COLOURING on such graphs is fixed-parameter tractable when parameterized by vertical bar H-1 vertical bar + vertical bar H-2 vertical bar. As a by-product, we obtain the same result both for the problem of determining a maximum independent set and for the problem of determining a maximum clique. (C) 2013 Elsevier B.V. All rights reserved.