The order of uniquely partitionable graphs
Izak Broere ; Marietjie Frick ; Peter Mihók
Discussiones Mathematicae Graph Theory, Tome 17 (1997), p. 115-125 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by Vi has property i. If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

Publié le : 1997-01-01
EUDML-ID : urn:eudml:doc:270714 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1044,
     author = {Izak Broere and Marietjie Frick and Peter Mih\'ok},
     title = {The order of uniquely partitionable graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {17},
     year = {1997},
     pages = {115-125},
     zbl = {0906.05058},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1044}
}

Izak Broere; Marietjie Frick; Peter Mihók. The order of uniquely partitionable graphs. Discussiones Mathematicae Graph Theory, Tome 17 (1997) pp. 115-125. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1044/

[000] [1] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely (m,k)τ-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. | Zbl 0870.05026

[001] [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa Internat. Publ., 1991) 41-68.

[002] [3] I. Broere and M. Frick, On the order of uniquely (k,m)-colourable graphs, Discrete Math. 82 (1990) 225-232, doi: 10.1016/0012-365X(90)90200-2. | Zbl 0712.05024

[003] [4] I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038. | Zbl 0902.05027

[004] [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986). | Zbl 0666.05001

[005] [6] M. Frick, On replete graphs, J. Graph Theory 16 (1992) 165-175, doi: 10.1002/jgt.3190160208. | Zbl 0763.05044

[006] [7] M. Frick and M.A. Henning, Extremal results on defective colourings of graphs, Discrete Math. 126 (1994) 151-158, doi: 10.1016/0012-365X(94)90260-7. | Zbl 0794.05029

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

[008] [9] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. | Zbl 0829.05057