Geodesic
On partitions of hereditary properties of graphs
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 3, pp. 377-387.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: hereditary property, acyclic colouring, Ramsey class 
@article{DMGT_2006_26_3_a2,
     author = {Borowiecki, Mieczys{\l}aw and Fiedorowicz, Anna},
     title = {On partitions of hereditary properties of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {377--387},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a2/}
}
TY  - JOUR
AU  - Borowiecki, Mieczysław
AU  - Fiedorowicz, Anna
TI  - On partitions of hereditary properties of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 377
EP  - 387
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a2/
LA  - en
ID  - DMGT_2006_26_3_a2
ER  - 
%0 Journal Article
%A Borowiecki, Mieczysław
%A Fiedorowicz, Anna
%T On partitions of hereditary properties of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 377-387
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a2/
%G en
%F DMGT_2006_26_3_a2
Borowiecki, Mieczysław; Fiedorowicz, Anna. On partitions of hereditary properties of graphs. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 3, pp. 377-387. http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a2/

[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:197::AID-JGT9>3.0.CO;2-O

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

[3] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3.

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

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

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

[7] M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobsc. Akad. Gruzin. SSR 93 (1979) 21-24 (in Russian).

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

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

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