# Factorizations of properties of graphs

Izak Broere; Samuel John Teboho Moagi; Peter Mihók; Roman Vasky

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 2, page 167-174
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzak Broere, et al. "Factorizations of properties of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 167-174. <http://eudml.org/doc/270424>.

@article{IzakBroere1999,

abstract = {A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph $G[V_i]$ has property $_i$. The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that = ₁∘₂∘...∘ₙ; otherwise is irreducible in . We study the structure of different lattices of properties of graphs and we prove that in these lattices every reducible property of graphs has a finite factorization into irreducible properties.},

author = {Izak Broere, Samuel John Teboho Moagi, Peter Mihók, Roman Vasky},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {factorization; property of graphs; irreducible property; reducible property; lattice of properties of graphs; partition; irreducible properties},

language = {eng},

number = {2},

pages = {167-174},

title = {Factorizations of properties of graphs},

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

volume = {19},

year = {1999},

}

TY - JOUR

AU - Izak Broere

AU - Samuel John Teboho Moagi

AU - Peter Mihók

AU - Roman Vasky

TI - Factorizations of properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 2

SP - 167

EP - 174

AB - A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph $G[V_i]$ has property $_i$. The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that = ₁∘₂∘...∘ₙ; otherwise is irreducible in . We study the structure of different lattices of properties of graphs and we prove that in these lattices every reducible property of graphs has a finite factorization into irreducible properties.

LA - eng

KW - factorization; property of graphs; irreducible property; reducible property; lattice of properties of graphs; partition; irreducible properties

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

ER -

## References

top- [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
- [2] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991), 42-69.
- [3] A. Haviar and R. Nedela, On varieties of graphs, Discuss. Math. Graph Theory 18 (1998) 209-223, doi: 10.7151/dmgt.1077. Zbl0926.05033
- [4] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
- [5] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [6] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, hypergraphs and matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
- [7] P. Mihók, G. Semanišin, Reducible Properties of Graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. Zbl0829.05057
- [8] P. Mihók, G. Semanišin and R. Vasky, Additive and Hereditary Properties of Graphs are Uniquely Factorizable into Irreducible Factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O Zbl0942.05056

## NotesEmbed ?

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