publication . Article . 2002

Three-colourbility and forbidden subgraphs. II: polynomial algorithms

Bert Randerath; Ingo Schiermeyer; Meike Tewes;
Open Access
  • Published: 01 May 2002 Journal: Discrete Mathematics, volume 251, issue 1-3, pages 137-153 (issn: 0012-365X, Copyright policy)
  • Publisher: Elsevier BV
In this paper we study the chromatic number for graphs with forbidden induced subgraphs. We focus our interest on graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colourability can be decided in polynomial time and, if so, a proper 3-colouring can be determined also in polynomial time. Note that the 3-colourability decision problem is a well-known NP-complete problem, even for special graph classes, e.g. triangle-free and K1,5-free (Discrete Math. 162 (1-3) (1996) 313). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-colouring of a given graph in general. We present t...
free text keywords: Theoretical Computer Science, Discrete Mathematics and Combinatorics, Line graph, law.invention, law, Perfect graph theorem, Butterfly graph, Forbidden graph characterization, Graph property, Combinatorics, Mathematics, Discrete mathematics, Comparability graph, Split graph, Tutte polynomial
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue