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

Abstract

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

How to cite

top

Bert 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. [1] J.A. Bondy and U.S.R. Murty, Graph Theory and Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  2. [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. [3] S. Brandt, Triangle-free graphs without forbidden subgraphs, Electronic Notes in Discrete Math. Vol. 3. Zbl1039.05508
  4. [4] P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38, doi: 10.4153/CJM-1959-003-9. 
  5. [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. [6] A. Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. XIX (1987) 413-441. Zbl0718.05041
  7. [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. [8] T.R. Jensen, B.Toft, Graph Colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  9. [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. [10] P. Mihók and I. Schiermeyer, Chromatic number of classes of graphs with prescribed cycle lengths, submitted. 
  11. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.