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 {H_1,H_2}, where we allow H_1 to have a single edge and H_2 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 |H_1| + |H_2|. 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.
展开▼
机译：图G =（V，E）的着色是映射c：V→{1,2，...}，如果uv∈E，则c（u）≠c（v）;如果| c（V）| ≤k，则c为k色。着色问题是测试给定图是否对某些给定整数k具有k色。如果某个图不包含某个族H中任何图的同构诱导子图，则称为无H。 | H |的无H图着色的复杂性= 1已被完全分类。当| H | = 2，尽管仍有许多部分结果是已知的，但分类仍然是开放的。我们继续进行这方面的研究，并禁止诱导子图{H_1，H_2}，其中我们允许H_1具有单个边，而H_2具有单个非边。我们证明了在用| H_1 |参数化时，此类图上的着色是固定参数可处理的，而不是仅显示多项式时间可解性。 + | H_2 |。作为副产品，对于确定最大独立集的问题和确定最大集团的问题，我们都得到相同的结果。
展开▼
