PDF
Discussiones Mathematicae Graph Theory 15(2) (1995)
195-203
DOI: https://doi.org/10.7151/dmgt.1017
ON THE FACTORIZATION OF REDUCIBLE PROPERTIES OF GRAPHS INTO IRREDUCIBLE FACTORS
P. Mihók and R. Vasky
Department of Geometry and Algebra
Faculty of Sciences, P. J. Šafárik's University
Jesenná 5, 04154 Košice, Slovak Republic
Abstract
A hereditary property R of graphs is said to be reducible if there exist hereditary properties P1,P2 such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V1∪V2 so that ⟨V1⟩ ∈ P1 and ⟨V2⟩ ∈ P2. The problem of the factorization of reducible properties into irreducible factors is investigated.
Keywords: hereditary property of graphs, additivity, reducibility, vertex partition.
1991 Mathematics Subject Classification: 05C15, 05C75.
References
| [1] | M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, 1991) 42-69. |
| [2] | T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). |
| [3] | P. Mihók, G. Semaniin, Reducible properties of graphs, Discussiones Math.- Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. |
| [4] | P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. |
| [5] | P. Mihók, On the minimal reducible bound for outerplanar and planar graphs (to appear). |
Close