Generalized ramsey theory and decomposable properties of graphs
Stefan A. Burr ; Michael S. Jacobson ; Peter Mihók ; Gabriel Semanišin
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 199-217 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270680 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1095,
     author = {Stefan A. Burr and Michael S. Jacobson and Peter Mih\'ok and Gabriel Semani\v sin},
     title = {Generalized ramsey theory and decomposable properties of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {199-217},
     zbl = {0958.05094},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1095}
}

Stefan A. Burr; Michael S. Jacobson; Peter Mihók; Gabriel Semanišin. Generalized ramsey theory and decomposable properties of graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 199-217. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1095/

[000] [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. | Zbl 0902.05026

[001] [2] M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs (manuscript) 1998. | Zbl 0905.05061

[002] [3] S.A. Burr, A ramsey-theoretic result involving chromatic numbers, J. Graph Theory 4 (1980) 241-242, doi: 10.1002/jgt.3190040212. | Zbl 0437.05023

[003] [4] S.A. Burr and M.S. Jacobson, Arrow relations involving partition parameters of graphs (manuscript) 1982.

[004] [5] S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congressus Numerantium 70 (1990) 159-170. | Zbl 0697.05046

[005] [6] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). | Zbl 0833.05001

[006] [7] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). | Zbl 0971.05046

[007] [8] T. Kövari, V.T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1969) 50-57. | Zbl 0055.00704

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

[009] [10] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. | Zbl 0202.23502

[010] [11] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442. | Zbl 0151.33401

[011] [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. | Zbl 0471.05038

[012] [13] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). | Zbl 1055.05061

[013] [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.