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/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory and Applications (Macmillan, London and Elsevier, New York, 1976).

[2] A. Brandstädt, Van Bang Le and J.P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications (SIAM, Philadelphia, PA, 1999).

[3] S. Brandt, Triangle-free graphs without forbidden subgraphs, Electronic Notes in Discrete Math. Vol. 3.

[4] P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38, doi: 10.4153/CJM-1959-003-9.

[5] P. Erdős, Some of my favourite unsolved problems, in: A. Baker, B. Bollobás and A. Hajnal, eds. A tribute to Paul Erdős (Cambridge Univ. Press, Cambridge, 1990) 467.

[6] A. Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. XIX (1987) 413-441.

[7] A. Gyárfás, Graphs with k odd cycle lengths, Discrete Math. 103 (1992) 41-48, doi: 10.1016/0012-365X(92)90037-G.

[8] T.R. Jensen, B.Toft, Graph Colouring problems (Wiley-Interscience Publications, New York, 1995).

[9] S.E. Markossian, G.S. Gasparian and B.A. Reed, β-Perfect Graphs, J. Combin. Theory (B) 67 (1996) 1-11, doi: 10.1006/jctb.1996.0030.

[10] P. Mihók and I. Schiermeyer, Chromatic number of classes of graphs with prescribed cycle lengths, submitted.

[11] I. Rusu, Berge graphs with chordless cycles of bounded length, J. Graph Theory 32 (1999) 73-79, doi: 10.1002/(SICI)1097-0118(199909)32:173::AID-JGT7>3.0.CO;2-7

[12] A.D. Scott, Induced Cycles and Chromatic Number, J. Combin. Theory (B) 76 (1999) 70-75, doi: 10.1006/jctb.1998.1894.

[13] D.P. Sumner, Subtrees of a Graph and the Chromatic Number, in: G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster, and D.R. Lick, eds, The Theory and Applications of Graphs, Proc. 4th International Graph Theory Conference (Kalamazoo, Michigan, 1980) 557-576, (Wiley, New York, 1981).