The order of uniquely partitionable graphs

• Autorzy: Izak Broere , Marietjie Frick , Peter Mihók
• Języki publikacji: EN

Abstrakty

EN

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 $V_i$ 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 𝓟₁,...,𝓟ₙ.

Słowa kluczowe

EN

hereditary property of graphs; uniquely partitionable graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1997
• Tom: 17
• Numer: 1
• Strony: 115-125

Daty

wydano

1997

otrzymano

1997-01-25

poprawiono

1997-03-24

Twórcy

autor

Izak Broere

• Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Aucklandpark, 2006 South Africa

autor

Marietjie Frick

• Department of Mathematics, Applied Mathematics and Astronomy, University of South Africa, P.O. Box 392, Pretoria, 0001 South Africa

autor

Peter Mihók

• Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

Bibliografia

• [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.
• [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa Internat. Publ., 1991) 41-68.
• [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.
• [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.
• [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986).
• [6] M. Frick, On replete graphs, J. Graph Theory 16 (1992) 165-175, doi: 10.1002/jgt.3190160208.
• [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.
• [8] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
• [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.

Identyfikatory

DOI

10.7151/dmgt.1044