Factorizations of properties of graphs

• Autorzy: Izak Broere , Samuel John Teboho Moagi , Peter Mihók , Roman Vasky
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

factorization; property of graphs; irreducible property; reducible property; lattice of properties of graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1999
• Tom: 19
• Numer: 2
• Strony: 167-174

Daty

wydano

1999

otrzymano

1999-02-02

poprawiono

1999-09-08

Twórcy

autor

Izak Broere

• Department of Mathematics, Faculty of Science, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa

autor

Samuel John Teboho Moagi

• Department of Mathematics, Faculty of Science, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa

autor

Peter Mihók

• Mathematical Institute, Slovak Academy of Sciences, Gresákova 6, Košice, Slovak Republic

autor

Roman Vasky

• Department of Geometry and Algebra, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

Bibliografia

• [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.
• [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.
• [4] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995).
• [5] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).
• [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.
• [7] P. Mihók, G. Semanišin, Reducible Properties of Graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.
• [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

Identyfikatory

DOI

10.7151/dmgt.1093