Acyclic reducible bounds for outerplanar graphs
Mieczysław Borowiecki ; Anna Fiedorowicz ; Mariusz Hałuszczak
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 219-239 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. G[Vi]∈i for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that u∈Vi and v∈Vj is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring. If ⊆ R, then we say that R is an acyclic reducible bound for . In this paper we present acyclic reducible bounds for the class of outerplanar graphs.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270253 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1443,
     author = {Mieczys\l aw Borowiecki and Anna Fiedorowicz and Mariusz Ha\l uszczak},
     title = {Acyclic reducible bounds for outerplanar graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {219-239},
     zbl = {1194.05127},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1443}
}

Mieczysław Borowiecki; Anna Fiedorowicz; Mariusz Hałuszczak. Acyclic reducible bounds for outerplanar graphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 219-239. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1443/

[000] [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 | Zbl 0929.05031

[001] [2] P. Boiron, E. Sopena and L. Vignal, Acyclic improper colourings of graphs with bounded degree, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 49 (1999) 1-9. | Zbl 0930.05042

[002] [3] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. | Zbl 0902.05026

[003] [4] M. Borowiecki and A. Fiedorowicz, On partitions of hereditary properties of graphs, Discuss. Math. Graph Theory 26 (2006) 377-387, doi: 10.7151/dmgt.1330. | Zbl 1139.05018

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

[005] [6] 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. | Zbl 0940.05032

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

[007] [8] R. Diestel, Graph Theory (Springer, Berlin, 1997).

[008] [9] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. | Zbl 0265.05103

[009] [10] D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001).