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 ! 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 classied. When jHj = 2, the classication 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.

Citation

Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013, December). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Presented at 39th International Workshop, WG 2013, Lübeck, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 39th International Workshop, WG 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 14, 2015
• Print ISSN: 0302-9743
• Pages: 201-212
• Series Title: Lecture notes in computer science
• Series Number: 8165
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers.
• ISBN: 9783642450426
• DOI: https://doi.org/10.1007/978-3-642-45043-3_18
• Public URL: https://durham-repository.worktribe.com/output/1153569