# Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki; Anna Fiedorowicz; Mariusz Hałuszczak

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 219-239
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMieczysław Borowiecki, Anna Fiedorowicz, and Mariusz Hałuszczak. "Acyclic reducible bounds for outerplanar graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 219-239. <http://eudml.org/doc/270253>.

@article{MieczysławBorowiecki2009,

abstract = {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[V_i] ∈ _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 ∈ V_i$ and $v ∈ V_j$ 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.},

author = {Mieczysław Borowiecki, Anna Fiedorowicz, Mariusz Hałuszczak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; acyclic colouring; additive hereditary class; outerplanar graph},

language = {eng},

number = {2},

pages = {219-239},

title = {Acyclic reducible bounds for outerplanar graphs},

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

volume = {29},

year = {2009},

}

TY - JOUR

AU - Mieczysław Borowiecki

AU - Anna Fiedorowicz

AU - Mariusz Hałuszczak

TI - Acyclic reducible bounds for outerplanar graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 219

EP - 239

AB - 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[V_i] ∈ _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 ∈ V_i$ and $v ∈ V_j$ 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.

LA - eng

KW - graph; acyclic colouring; additive hereditary class; outerplanar graph

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

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 Ser. Discrete Math. Theoret. Comput. Sci. 49 (1999) 1-9. Zbl0930.05042
- [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. Zbl0902.05026
- [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. Zbl1139.05018
- [5] 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
- [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. Zbl0940.05032
- [7] M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobsc. Akad. Nauk Gruzin SSR 93 (1979) 21-24 (in Russian).
- [8] R. Diestel, Graph Theory (Springer, Berlin, 1997).
- [9] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
- [10] D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001).