Colouring of graphs with Ramsey-type forbidden subgraphs

详细信息    查看全文

• 作者：Konrad K. Dabrowski ; Petr A. Golovach ; Daniel Paulusma
• 关键词：Colouring ; Independent set ; Clique ; Forbidden induced subgraphs
• 刊名：Theoretical Computer Science
• 出版年：20 February, 2014
• 年：2014
• 卷：522
• 期：Complete
• 页码：34-43
• 全文大小：321 K

文摘

A colouring of a graph is a mapping such that if ; if 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 , then it is called -free. The complexity of Colouring for -free graphs with has been completely classified. When , the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs , where we allow to have a single edge and 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 . 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.