DMGT

Discussiones Mathematicae Graph Theory 21(1) (2001) 267-281
DOI: https://doi.org/10.7151/dmgt.1149

COLOURING GRAPHS WITH PRESCRIBED INDUCED CYCLE LENGTHS

Bert Randerath

Institut für Informatik
Universität zu Köln
D-50969 Köln, Germany
e-mail: randerath@informatik.uni-koeln.de

Ingo Schiermeyer

Fakultät für Mathematik und Informatik
TU Bergakademie Freiberg
D-09596 Freiberg, Germany
e-mail: schierme@mathe.tu-freiberg.de

Abstract

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 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 G^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 ∈ 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 G^I(n₁,n₂). Here we obtain the surprising result that there exists no linear χ-binding function for G^I(3,4).

Keywords: colouring, chromatic number, induced subgraphs, graph algorithms, χ-binding function.

2000 Mathematics Subject Classification: 05C15, 05C75, 05C85.

References

[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:1<73::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).

Received 28 December 2000
Revised 13 May 2001