Reducible properties of graphs
P. Mihók ; G. Semanišin
Discussiones Mathematicae Graph Theory, Tome 15 (1995), p. 11-18 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1995-01-01
EUDML-ID : urn:eudml:doc:270454 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1002,
     author = {P. Mih\'ok and G. Semani\v sin},
     title = {Reducible properties of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {15},
     year = {1995},
     pages = {11-18},
     zbl = {0829.05057},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1002}
}

P. Mihók; G. Semanišin. Reducible properties of graphs. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 11-18. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1002/

[000] [1] V. E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskretnaja matematika 4 (1992) 148-157 (Russian). | Zbl 0766.05088

[001] [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs in: Advances in Graph Theory, Vishwa International Publication, India, (1991) 42-69.

[002] [3] G. Chartrand, L. Lesniak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey California 1986). | Zbl 0666.05001

[003] [4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. | Zbl 0623.05043

[004] [5] P. Mihók, An extension of Brook's theorem, Annals of Discrete Math. 51 (1992) 235-236. | Zbl 0766.05028

[005] [6] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, (to appear). | Zbl 0911.05043

[006] [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.

[007] [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. | Zbl 0609.05057

[008] [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. | Zbl 0811.05048