PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 19 | 2 | 199-217
Tytuł artykułu

Generalized ramsey theory and decomposable properties of graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
Wydawca
Rocznik
Tom
19
Numer
2
Strony
199-217
Opis fizyczny
Daty
wydano
1999
otrzymano
1999-02-02
poprawiono
1999-09-08
Twórcy
  • Department of Computer Science, City College, C.U.N.Y. New York, NY 10031, U.S.A.
  • University of Louisville, Louisville, KY 40292, U.S.A.
autor
  • Mathematical Institute, Slovak Academy of Sciences, Gresákova 6, 040 01 Košice, Slovak Republic
  • Department of Geometry and Algebra, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic
Bibliografia
  • [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
  • [2] M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs (manuscript) 1998.
  • [3] S.A. Burr, A ramsey-theoretic result involving chromatic numbers, J. Graph Theory 4 (1980) 241-242, doi: 10.1002/jgt.3190040212.
  • [4] S.A. Burr and M.S. Jacobson, Arrow relations involving partition parameters of graphs (manuscript) 1982.
  • [5] S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congressus Numerantium 70 (1990) 159-170.
  • [6] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995).
  • [7] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).
  • [8] T. Kövari, V.T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1969) 50-57.
  • [9] J. Kratochvíl, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties, Discuss. Math. Graph Theory 17 (1997) 77-88, doi: 10.7151/dmgt.1040.
  • [10] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715.
  • [11] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442.
  • [12] P. Mihók, On graphs critical with respect to vertex partition numbers, Discrete Math. 37 (1981) 123-126, doi: 10.1016/0012-365X(81)90146-1.
  • [13] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted).
  • [14] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected topics in graph theory vol. 2 (Academic Press, London, 1983) 161-200.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1095
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ć.