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

Abstract

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

How to cite

top

Mieczysł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. [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. [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. [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. [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. [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. [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. [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. [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. [9] R. Diestel, Graph Theory (Springer, Berlin, 1997). 
  10. [10] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
  11. [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

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.