# Colouring graphs with prescribed induced cycle lengths

Bert Randerath; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 267-281
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBert Randerath, and Ingo Schiermeyer. "Colouring graphs with prescribed induced cycle lengths." Discussiones Mathematicae Graph Theory 21.2 (2001): 267-281. <http://eudml.org/doc/270350>.

@article{BertRanderath2001,

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 $^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)$.},

author = {Bert Randerath, Ingo Schiermeyer},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {colouring; chromatic number; induced subgraphs; graph algorithms; χ-binding function; polynomial time algorithms; -binding function},

language = {eng},

number = {2},

pages = {267-281},

title = {Colouring graphs with prescribed induced cycle lengths},

url = {http://eudml.org/doc/270350},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Bert Randerath

AU - Ingo Schiermeyer

TI - Colouring graphs with prescribed induced cycle lengths

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 267

EP - 281

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

LA - eng

KW - colouring; chromatic number; induced subgraphs; graph algorithms; χ-binding function; polynomial time algorithms; -binding function

UR - http://eudml.org/doc/270350

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory and Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
- [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). Zbl0919.05001
- [3] S. Brandt, Triangle-free graphs without forbidden subgraphs, Electronic Notes in Discrete Math. Vol. 3. Zbl1039.05508
- [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. Zbl0709.11003
- [6] A. Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. XIX (1987) 413-441. Zbl0718.05041
- [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. Zbl0773.05072
- [8] T.R. Jensen, B.Toft, Graph Colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [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. Zbl0857.05038
- [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 Zbl0929.05035
- [12] A.D. Scott, Induced Cycles and Chromatic Number, J. Combin. Theory (B) 76 (1999) 70-75, doi: 10.1006/jctb.1998.1894. Zbl0936.05041
- [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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.