# On partitions of hereditary properties of graphs

Mieczysław Borowiecki; Anna Fiedorowicz

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 3, page 377-387
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMieczysław Borowiecki, and Anna Fiedorowicz. "On partitions of hereditary properties of graphs." Discussiones Mathematicae Graph Theory 26.3 (2006): 377-387. <http://eudml.org/doc/270628>.

@article{MieczysławBorowiecki2006,

abstract = {In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement, in some sense, of that in Theorem is given.},

author = {Mieczysław Borowiecki, Anna Fiedorowicz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary property; acyclic colouring; Ramsey class},

language = {eng},

number = {3},

pages = {377-387},

title = {On partitions of hereditary properties of graphs},

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

volume = {26},

year = {2006},

}

TY - JOUR

AU - Mieczysław Borowiecki

AU - Anna Fiedorowicz

TI - On partitions of hereditary properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 3

SP - 377

EP - 387

AB - In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement, in some sense, of that in Theorem is given.

LA - eng

KW - hereditary property; acyclic colouring; Ramsey class

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

ER -

## References

top- [1] P. Boiron, E. Sopena and L. Vignal, Acyclic improper colorings of graphs, J. Graph Theory 32 (1999) 97-107, doi: 10.1002/(SICI)1097-0118(199909)32:1<97::AID-JGT9>3.0.CO;2-O Zbl0929.05031
- [2] P. Boiron, E. Sopena and L. Vignal, Acyclic improper colourings of graphs with bounded degree, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49 (1999) 1-9. Zbl0930.05042
- [3] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3. Zbl0406.05031
- [4] O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic colourings of 1-planar graphs, Discrete Applied Math. 114 (2001) 29-41, doi: 10.1016/S0166-218X(00)00359-0. Zbl0996.05053
- [5] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Acyclic colorings of planar graphs with large girth, J. London Math. Soc. 60 (1999) 344-352, doi: 10.1112/S0024610799007942. Zbl0940.05032
- [6] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
- [7] M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobsc. Akad. Gruzin. SSR 93 (1979) 21-24 (in Russian). Zbl0397.05023
- [8] G. Ding, B. Oporowski, D.P. Sanders and D. Vertigan, Partitioning graphs of bounded tree-width, Combinatorica 18 (1998) 1-12, doi: 10.1007/s004930050001. Zbl0924.05022
- [9] R. Diestel, Graph Theory (Springer, Berlin, 1997).
- [10] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
- [11] P. Mihók and G. Semanišin, Reducible properties of graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. Zbl0829.05057

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