ArticleOriginal scientific text
Title
On the factorization of reducible properties of graphs into irreducible factors
Authors 1, 1
Affiliations
- Department of Geometry and Algebra, Faculty of Sciences, P. J. Šafárik's University
Abstract
A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
Keywords
hereditary property of graphs, additivity, reducibility, vertex partition
Bibliography
- M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, 1991) 42-69.
- T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).
- P. Mihók, G. Semaniin, Reducible properties of graphs, Discussiones Math.- Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.
- P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
- P. Mihók, On the minimal reducible bound for outerplanar and planar graphs (to appear).
Pages:
195-203
Main language of publication
English
Received
1995-05-10
Published
1995
Exact and natural sciences