Colouring graphs with prescribed induced cycle lengths
Bert Randerath ; Ingo Schiermeyer
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 267-281 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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).

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270350 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1149,
     author = {Bert Randerath and Ingo Schiermeyer},
     title = {Colouring graphs with prescribed induced cycle lengths},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {267-281},
     zbl = {1002.05026},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1149}
}

Bert Randerath; Ingo Schiermeyer. Colouring graphs with prescribed induced cycle lengths. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 267-281. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1149/

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

[001] [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). | Zbl 0919.05001

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

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

[004] [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. | Zbl 0709.11003

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

[006] [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. | Zbl 0773.05072

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

[008] [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. | Zbl 0857.05038

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

[010] [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 | Zbl 0929.05035

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

[012] [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).