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

Abstract

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

How to cite

top

Stefan 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. [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. [2] M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs (manuscript) 1998. Zbl0905.05061
  3. [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. [4] S.A. Burr and M.S. Jacobson, Arrow relations involving partition parameters of graphs (manuscript) 1982. 
  5. [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. [6] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
  7. [7] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  8. [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. [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. [10] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. Zbl0202.23502
  11. [11] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442. Zbl0151.33401
  12. [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. [13] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). Zbl1055.05061
  14. [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. 

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.