Colouring of graphs with Ramsey-type forbidden subgraphs

Dabrowski, K.K.; Golovach, P.A.; Paulusma, D.

Abstract

A colouring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that c(u)≠c(v) if uv∈E; if |c(V)|⩽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 |H|=1 has been completely classified. When |H|=2, the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs {H1,H2}, where we allow H1 to have a single edge and H2 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 |H1|+|H2|. 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.

Citation

Dabrowski, K., Golovach, P., & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522, 34-43. https://doi.org/10.1016/j.tcs.2013.12.004

• Journal Article Type: Article
• Publication Date: Feb 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 8, 2015
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 522
• Pages: 34-43
• DOI: https://doi.org/10.1016/j.tcs.2013.12.004
• Keywords: Colouring, Independent set, Clique, Forbidden induced subgraphs.
• Public URL: https://durham-repository.worktribe.com/output/1417570