Skip to main content

Research Repository

Advanced Search

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs

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

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs Thumbnail


Authors

K. K. Dabrowski

P. A. Golovach



Contributors

Andreas Brandstädt
Editor

Klaus Jansen
Editor

Rüdiger Reischuk
Editor

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). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers (201-212). https://doi.org/10.1007/978-3-642-45043-3_18

Conference Name 39th International Workshop, WG 2013
Conference Location Lübeck, Germany
Publication Date Jan 1, 2013
Deposit Date Dec 20, 2014
Publicly Available Date Mar 28, 2024
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

Files





You might also like



Downloadable Citations