Acyclic reducible bounds for outerplanar graphs

• Autorzy: Mieczysław Borowiecki , Anna Fiedorowicz , Mariusz Hałuszczak
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph; acyclic colouring; additive hereditary class; outerplanar graph

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C35: Extremal problems
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 2
• Strony: 219-239

Daty

wydano

2009

otrzymano

2007-12-13

poprawiono

2008-07-04

zaakceptowano

2008-10-23

Twórcy

autor

Mieczysław Borowiecki

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

autor

Anna Fiedorowicz

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

autor

Mariusz Hałuszczak

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1443