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

Abstract

top
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.

How to cite

top

Mieczysł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. [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. [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. [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. [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. [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. [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. [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. [8] R. Diestel, Graph Theory (Springer, Berlin, 1997). 
  9. [9] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
  10. [10] D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.