# Generalized ramsey theory and decomposable properties of graphs

Stefan A. Burr; Michael S. Jacobson; Peter Mihók; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 2, page 199-217
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topStefan A. Burr, et al. "Generalized ramsey theory and decomposable properties of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 199-217. <http://eudml.org/doc/270680>.

@article{StefanA1999,

abstract = {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.},

author = {Stefan A. Burr, Michael S. Jacobson, Peter Mihók, Gabriel Semanišin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary properties; additivity; reducibility; decomposability; Ramsey number; graph invariants; graph theoretical invariants; decomposable properties; generalized Ramsey numbers},

language = {eng},

number = {2},

pages = {199-217},

title = {Generalized ramsey theory and decomposable properties of graphs},

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

volume = {19},

year = {1999},

}

TY - JOUR

AU - Stefan A. Burr

AU - Michael S. Jacobson

AU - Peter Mihók

AU - Gabriel Semanišin

TI - Generalized ramsey theory and decomposable properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 2

SP - 199

EP - 217

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

LA - eng

KW - hereditary properties; additivity; reducibility; decomposability; Ramsey number; graph invariants; graph theoretical invariants; decomposable properties; generalized Ramsey numbers

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

ER -

## References

top- [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. Zbl0902.05026
- [2] M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs (manuscript) 1998. Zbl0905.05061
- [3] S.A. Burr, A ramsey-theoretic result involving chromatic numbers, J. Graph Theory 4 (1980) 241-242, doi: 10.1002/jgt.3190040212. Zbl0437.05023
- [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. Zbl0697.05046
- [6] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
- [7] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [8] T. Kövari, V.T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1969) 50-57. Zbl0055.00704
- [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. Zbl0905.05038
- [10] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. Zbl0202.23502
- [11] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442. Zbl0151.33401
- [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. Zbl0471.05038
- [13] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). Zbl1055.05061
- [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.

## Citations in EuDML Documents

top## NotesEmbed ?

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