# Reducible properties of graphs

Discussiones Mathematicae Graph Theory (1995)

- Volume: 15, Issue: 1, page 11-18
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topP. Mihók, and G. Semanišin. "Reducible properties of graphs." Discussiones Mathematicae Graph Theory 15.1 (1995): 11-18. <http://eudml.org/doc/270454>.

@article{P1995,

abstract = {Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.},

author = {P. Mihók, G. Semanišin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary property of graphs; additivity; reducibility; additive properties of graphs; reducible property; hereditary property; cancellation problem},

language = {eng},

number = {1},

pages = {11-18},

title = {Reducible properties of graphs},

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

volume = {15},

year = {1995},

}

TY - JOUR

AU - P. Mihók

AU - G. Semanišin

TI - Reducible properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1995

VL - 15

IS - 1

SP - 11

EP - 18

AB - Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

LA - eng

KW - hereditary property of graphs; additivity; reducibility; additive properties of graphs; reducible property; hereditary property; cancellation problem

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

ER -

## References

top- [1] V. E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskretnaja matematika 4 (1992) 148-157 (Russian). Zbl0766.05088
- [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs in: Advances in Graph Theory, Vishwa International Publication, India, (1991) 42-69.
- [3] G. Chartrand, L. Lesniak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey California 1986). Zbl0666.05001
- [4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
- [5] P. Mihók, An extension of Brook's theorem, Annals of Discrete Math. 51 (1992) 235-236. Zbl0766.05028
- [6] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, (to appear). Zbl0911.05043
- [7] M. Simonovits, Extremal graph theory, in: L. W. Beineke and R. J. Wilson eds. Selected Topics in Graph Theory 2 (Academic Press, London, 1983) 161-200.
- [8] E. R. Scheinerman, On the structure of hereditary classes of graphs, Journal of Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. Zbl0609.05057
- [9] E. R. Scheinerman, J. Zito, On the size of hereditary classes of graphs, J. Combin. Theory (B) 61 (1994) 16-39, doi: 10.1006/jctb.1994.1027. Zbl0811.05048

## Citations in EuDML Documents

top- P. Mihók, R. Vasky, On the factorization of reducible properties of graphs into irreducible factors
- Jan Kratochvíl, Peter Mihók, Gabriel Semanišin, Graphs maximal with respect to hom-properties
- Izak Broere, Marietjie Frick, Peter Mihók, The order of uniquely partitionable graphs
- Mieczysław Borowiecki, Anna Fiedorowicz, On partitions of hereditary properties of graphs
- Izak Broere, Marietjie Frick, Gabriel Semanišin, Maximal graphs with respect to hereditary properties
- Gabriel Semanišin, On some variations of extremal graph problems
- Izak Broere, Samuel John Teboho Moagi, Peter Mihók, Roman Vasky, Factorizations of properties of graphs
- Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin, A survey of hereditary properties of graphs

## NotesEmbed ?

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