|
 |
"Colouring Graphs with Prescribed Induced Cycle Lengths" |
|
Article by Bert Randerath, Ingo Schiermeyer, available as BibTeX Source, postscript file and compressed postscript file.
|
| Preprint Key: |
zpr98-341 |
| Keywords: |
chromatic number, colouring, cycle lengths, graph algorithms, induced subgraphs |
This article was published in 2001 in the journal "Discussiones Mathematicae", volume 21, pages 267-282.
|
Abstract: |
In this paper we study the chromatic number for graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P5-free and triangle-free, P6-free and C6-free graphs are 3-colourable. A canonical extension of these graph classes is {cal{G}}^I(4,5), the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of {cal{G}}^I(4,5) are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind. Thus, every Gin {cal{G}}^I(n_1,n_2) with n_1,n_2geq 4 is 3-colourable. Furthermore, we consider the related problem of finding a chi-binding function for the class {cal G}^I(n_1,n_2). An extended abstract of this paper appeared in SODA '99.
|
