publication . Article . 2004

3-Colorability ∈ P for P 6 -free graphs

Randerath, Bert; Schiermeyer, Ingo;
Restricted
  • Published: 01 Feb 2004 Journal: Discrete Applied Mathematics, volume 136, pages 299-313 (issn: 0166-218X, Copyright policy)
  • Publisher: Elsevier BV
Abstract
AbstractIn this paper, we study a chromatic aspect for the class of P6-free graphs. Here, the focus of our interest are graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colorability can be decided in polynomial time and, if so, a proper 3-coloring can be determined also in polynomial time. Note that the 3-colorability decision problem is a well-known NP-complete problem, even for special graph classes, e.g. for triangle- and K1,5-free graphs (Discrete Math. 162 (1–3) (1996) 313–317). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-coloring of a given graph in general....
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Applied Mathematics, Discrete Mathematics and Combinatorics, Indifference graph, Pathwidth, Forbidden graph characterization, Combinatorics, Graph coloring, 1-planar graph, Discrete mathematics, Split graph, Chordal graph, Cograph, Mathematics, Line graph, law.invention, law, 3-Colorability, Coloring algorithms, Perfect graphs, Graph classes
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue