Colouring Graphs with Prescribed Induced Cycle Lengths

Randerath, Bert and Schiermeyer, Ingo (2001) Colouring Graphs with Prescribed Induced Cycle Lengths.
Published in: Discussiones Mathematicae Vol. 21 (2). pp. 267-282.


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.

Download: [img] Postscript - Preprinted Version
Download (236kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: zpr98-341
Depositing User: Bert Randerath
Date Deposited: 27 Apr 2004 00:00
Last Modified: 19 Dec 2011 09:46