Determining the chromatic number of triangle-free 2P(3)-free graphs in polynomial time

作者：Broersma Hajo; Golovach Petr A; Paulusma Daniel^*; Song Jian

来源：Theoretical Computer Science, 2012, 423: 1-10.

DOI：10.1016/j.tcs.2011.12.076

• Chromatic number
• Triangle-free
• Forbidden induced subgraph

Let 2P(3) denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The VERTEX COLORING problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H-free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H = 2P(3). This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.

• 出版日期2012-3-16