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 条

[11]

Golovach Petr A., 2011, Fundamentals of Computation Theory. Proceedings 18th International Symposium, FCT 2011, P193, DOI 10.1007/978-3-642-22953-4_17

[12]

Grotschel M., 1984, ANN DISCRETE MATH, V21, P325, DOI [10.1016/S0304-0208(08)72943-8, DOI 10.1016/S0304-0208(08)72943-8]

[13] Deciding k-Colorability of P 5-Free Graphs in Polynomial Time [J].

Hoang, Chinh T. ;

Kaminski, Marcin ;

Lozin, Vadim ;

Sawada, Joe ;

Shu, Xiao .

ALGORITHMICA, 2010, 57 (01) :74-81

[14] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[15]

Kaminski M., 2007, ALGORITHMIC OPER RES, V21

[16]

Kral D., 2001, LECT NOTES COMPUT SC, V2001, P254, DOI DOI 10.1007/3-540-45477-223

[17] On the complexity of 4-coloring graphs without long induced paths [J].

Le, Van Bang ;

Randerath, Bert ;

Schiermeyer, Ingo .

THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) :330-335

[18] NP COMPLETENESS OF FINDING THE CHROMATIC INDEX OF REGULAR GRAPHS [J].

LEVEN, D ;

GALIL, Z .

JOURNAL OF ALGORITHMS, 1983, 4 (01) :35-44

[19]

Lozin V., 2007, Contrib. Discrete Math, V2, P61

[20] On the NP-completeness of the k-colorability problem for triangle-free graphs [J].

Maffray, F ;

Preissmann, M .

DISCRETE MATHEMATICS, 1996, 162 (1-3) :313-317

← 1 2 3 →