Geodesic
Colouring graphs with prescribed induced cycle lengths
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 267-281

Voir la notice de l'article provenant de la source Library of Science

In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is ^I(4,5), the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of ^I(4,5) are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every G ∈ ^I(n₁,n₂) with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class ^I(n₁,n₂). Here we obtain the surprising result that there exists no linear χ-binding function for ^I(3,4).
Keywords: colouring, chromatic number, induced subgraphs, graph algorithms, χ-binding function 
@article{DMGT_2001_21_2_a10,
     author = {Randerath, Bert and Schiermeyer, Ingo},
     title = {Colouring graphs with prescribed induced cycle lengths},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {267--281},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a10/}
}
TY  - JOUR
AU  - Randerath, Bert
AU  - Schiermeyer, Ingo
TI  - Colouring graphs with prescribed induced cycle lengths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 267
EP  - 281
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a10/
LA  - en
ID  - DMGT_2001_21_2_a10
ER  - 
%0 Journal Article
%A Randerath, Bert
%A Schiermeyer, Ingo
%T Colouring graphs with prescribed induced cycle lengths
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 267-281
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a10/
%G en
%F DMGT_2001_21_2_a10
Randerath, Bert; Schiermeyer, Ingo. Colouring graphs with prescribed induced cycle lengths. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 267-281. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a10/