The order of uniquely partitionable graphs

Izak Broere; Marietjie Frick; Peter Mihók

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 115-125
  • ISSN: 2083-5892

Abstract

top
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 ₁,...,ₙ.

How to cite

top

Izak Broere, Marietjie Frick, and Peter Mihók. "The order of uniquely partitionable graphs." Discussiones Mathematicae Graph Theory 17.1 (1997): 115-125. <http://eudml.org/doc/270714>.

@article{IzakBroere1997,
abstract = {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 ₁,...,ₙ.},
author = {Izak Broere, Marietjie Frick, Peter Mihók},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary property of graphs; uniquely partitionable graphs; partition},
language = {eng},
number = {1},
pages = {115-125},
title = {The order of uniquely partitionable graphs},
url = {http://eudml.org/doc/270714},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Izak Broere
AU - Marietjie Frick
AU - Peter Mihók
TI - The order of uniquely partitionable graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 115
EP - 125
AB - 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 ₁,...,ₙ.
LA - eng
KW - hereditary property of graphs; uniquely partitionable graphs; partition
UR - http://eudml.org/doc/270714
ER -

References

top
  1. [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. Zbl0870.05026
  2. [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa Internat. Publ., 1991) 41-68. 
  3. [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. Zbl0712.05024
  4. [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. Zbl0902.05027
  5. [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
  6. [6] M. Frick, On replete graphs, J. Graph Theory 16 (1992) 165-175, doi: 10.1002/jgt.3190160208. Zbl0763.05044
  7. [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. Zbl0794.05029
  8. [8] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
  9. [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. Zbl0829.05057

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.