4-coloring H-free graphs when H is small

被引：16

作者：

Golovach, Petr A. ^{[1
]}

Paulusma, Daniel ^{[1
]}

Song, Jian ^{[1
]}

机构：

[1] Univ Durham, Sci Labs, Sch Engn & Comp Sci, Durham DH1 3LE, England

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 1-2期

基金：

英国工程与自然科学研究理事会;

关键词：

Graph coloring; Forbidden induced subgraph; Linear forest; Polynomial-time algorithm; NP-COMPLETENESS; COLORING GRAPHS; K-COLORABILITY; COMPLEXITY; 3-COLORABILITY; ALGORITHM;

D O I：

10.1016/j.dam.2012.08.022

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The k-COLORING problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most six vertices, it is known that 3-COLORING is polynomial-time solvable on H-free graphs whenever H is a linear forest, and NP-complete otherwise. By solving the missing case P-2 + P-3, we prove the same result for 4-COLORING provided that H is a fixed graph on at most five vertices. (c) 2012 Elsevier B.V. All rights reserved.

引用

页码：140 / 150

页数：11

共 26 条

[1] ON GRAPHS WITH POLYNOMIALLY SOLVABLE MAXIMUM-WEIGHT CLIQUE PROBLEM [J].

BALAS, E ;

YU, CS .

NETWORKS, 1989, 19 (02) :247-253

[2]

Bondy JA, 2008, Grad. Texts Math, V244, DOI DOI 10.1007/978-1-84628-970-5

[3] Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time [J].

Broersma, Hajo ;

Golovach, Petr A. ;

Paulusma, Daniel ;

Song, Jian .

THEORETICAL COMPUTER SCIENCE, 2012, 423 :1-10

[4] Updating the complexity status of coloring graphs without a fixed induced linear forest [J].

Broersma, Hajo ;

Golovach, Petr A. ;

Paulusma, Daniel ;

Song, Jian .

THEORETICAL COMPUTER SCIENCE, 2012, 414 (01) :9-19

[5]

Broersma H, 2009, LECT NOTES COMPUT SC, V5874, P95, DOI 10.1007/978-3-642-10217-2_12

[6]

Bruce D, 2009, LECT NOTES COMPUT SC, V5878, P594, DOI 10.1007/978-3-642-10631-6_61

[7]

Couturier J. F., 2012, LNCS, V6986, P119

[8] On the parameterized complexity of coloring graphs in the absence of a linear forest [J].

Couturier, Jean-Francois ;

Golovach, Petr A. ;

Kratsch, Dieter ;

Paulusma, Daniel .

JOURNAL OF DISCRETE ALGORITHMS, 2012, 15 :56-62

[9] Colouring vertices of triangle-free graphs without forests [J].

Dabrowski, Konrad K. ;

Lozin, Vadim ;

Raman, Rajiv ;

Ries, Bernard .

DISCRETE MATHEMATICS, 2012, 312 (07) :1372-1385

[10] THE COMPLEXITY OF COLORING PROBLEMS ON DENSE GRAPHS [J].

EDWARDS, K .

THEORETICAL COMPUTER SCIENCE, 1986, 43 (2-3) :337-343

← 1 2 3 →