کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434471 689740 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Colouring of graphs with Ramsey-type forbidden subgraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Colouring of graphs with Ramsey-type forbidden subgraphs
چکیده انگلیسی

A colouring of a graph G=(V,E)G=(V,E) is a mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) if uv∈Euv∈E; if |c(V)|⩽k|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 HH, then it is called HH-free. The complexity of Colouring for HH-free graphs with |H|=1|H|=1 has been completely classified. When |H|=2|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}{H1,H2}, where we allow H1H1 to have a single edge and H2H2 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||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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 522, 20 February 2014, Pages 34–43
نویسندگان
, , ,