PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 267-281
Tytuł artykułu

Colouring graphs with prescribed induced cycle lengths

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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)$.
Wydawca
Rocznik
Tom
21
Numer
2
Strony
267-281
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-12-28
poprawiono
2001-05-13
Twórcy
  • Institut für Informatik, Universität zu Köln, D-50969 Köln, Germany
  • Fakultät für Mathematik und Informatik, TU Bergakademie Freiberg, D-09596 Freiberg, Germany
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1149
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.