PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2009 | 29 | 2 | 219-239
Tytuł artykułu

### Acyclic reducible bounds for outerplanar graphs

Autorzy
Treść / Zawartość
Warianty tytułu
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
219-239
Opis fizyczny
Daty
wydano
2009
otrzymano
2007-12-13
poprawiono
2008-07-04
zaakceptowano
2008-10-23
Twórcy
• Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z. Szafrana 4a, Zielona Góra, Poland
autor
• Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z. Szafrana 4a, Zielona Góra, Poland
autor
• 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).
Typ dokumentu
Bibliografia
Identyfikatory