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.

• Publication type: Conference Paper
• ISSN/ISBN: 0302-9743 (print), 1611-3349 (electronic), 978-3-642-45042-6 (print), 978-3-642-45043-3 (electronic)
• DOI: 10.1007/978-3-642-45043-3_18
• Further publication details on publisher web site
• Durham Research Online (DRO) - may include full text

Author(s) from Durham

• Professor Daniel Paulusma
• Dr Konrad Dabrowski

Abstract

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.