We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details

Dabrowski, K.K., Golovach, P.A. & Paulusma, D. (2013), Colouring of Graphs with Ramsey-Type Forbidden Subgraphs, in Brandstädt, Andreas, Jansen, Klaus, & Reischuk, Rüdiger eds, Lecture Notes in Computer Science 8165: 39th International Workshop, WG 2013. Lübeck, Germany, Springer, Lübeck, 201-212.

Author(s) from Durham


A colouring of a graph G = (V;E) is a mapping c : V !
f1; 2; : : :g such that c(u) 6= c(v) if uv 2 E; if jc(V )j  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
jHj = 1 has been completely classi ed. When jHj = 2, the classi cation
is still wide open, although many partial results are known. We
continue this line of research and forbid induced subgraphs fH1;H2g,
where we allow H1 to have a single edge and H2 to have a single nonedge.
Instead of showing only polynomial-time solvability, we prove that
Colouring on such graphs is xed-parameter tractable when parameterized
by jH1j + jH2j. As a byproduct, we obtain the same result both
for the problem of determining a maximum independent set and for the
problem of determining a maximum clique.