DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 15(2) (1995) 195-203
DOI: 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).