Can I read Three-colourability and forbidden subgraphs. II: polynomial algorithms on EtoBox?
Three-colourability and forbidden subgraphs. II: polynomial algorithms by Bert Randerath; Ingo Schiermeyer; Meike Tewes is a Computer Science article available to read on EtoBox.
What is Three-colourability and forbidden subgraphs. II: polynomial algorithms about?
In this paper we study the chromatic number for graphs with forbidden induced subgraphs. We focus our interest on graph classes (deÿned 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 three di erent approaches to reach our goal. The ÿrst approach is purely a structural analysis of the graph class in consideration; the second one is a structural analysis of only the non-perfect K4-free members of the considered graph class; ÿnally the last approach is based on propositional logic and bounded dominating subgraphs.
Who reads Three-colourability and forbidden subgraphs. II: polynomial algorithms?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Bert Randerath; Ingo Schiermeyer; Meike Tewes
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)
- Published
- 2002
- Language
- EN
- Field
- Computer Science (Physical Sciences)