DMGT

Discussiones Mathematicae Graph Theory 29(2) (2009) 219-239
DOI: https://doi.org/10.7151/dmgt.1443

ACYCLIC REDUCIBLE BOUNDS FOR OUTERPLANAR GRAPHS

Mieczysław Borowiecki, Anna Fiedorowicz and Mariusz Hałuszczak

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Z. Szafrana 4a, Zielona Góra, Poland

e-mail:	M.Borowiecki@wmie.uz.zgora.pl
	A.Fiedorowicz@wmie.uz.zgora.pl
	M.Hałuszczak@wmie.uz.zgora.pl

Abstract

For a given graph G and a sequence P₁, P₂,…, P_n of additive hereditary classes of graphs we define an acyclic (P₁, P₂,…,P_n)-colouring of G as a partition (V₁, V₂,…,V_n) of the set V(G) of vertices which satisfies the following two conditions:

G[V_i] ∈ P_i for i = 1,…,n,
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 = P₁⊗P₂⊗…⊗ P_n is defined as the set of the graphs having an acyclic (P₁, P₂,…,P_n)-colouring. If P ⊆ R, then we say that R is an acyclic reducible bound for P.

In this paper we present acyclic reducible bounds for the class of outerplanar graphs.

Keywords: graph, acyclic colouring, additive hereditary class, outerplanar graph.

2000 Mathematics Subject Classification: 05C75, 05C15, 05C35.

References

[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.
[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.
[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.
[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.
[5]	O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3.
[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.
[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.
[10]	D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001).

Received 13 December 2007
Revised 4 July 2008
Accepted 23 October 2008