Geodesic
Uniquely partitionable graphs
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 103-113

Voir la notice de l'article provenant de la source Library of Science

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph G[V_i] induced by V_i has property _i; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.
Keywords: hereditary property of graphs, additivity, reducibility, vertex partition 
@article{DMGT_1997_17_1_a6,
     author = {Bucko, Jozef and Frick, Marietjie and Mih\'ok, Peter and Vasky, Roman},
     title = {Uniquely partitionable graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {103--113},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {1997},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a6/}
}
TY  - JOUR
AU  - Bucko, Jozef
AU  - Frick, Marietjie
AU  - Mihók, Peter
AU  - Vasky, Roman
TI  - Uniquely partitionable graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 103
EP  - 113
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a6/
LA  - en
ID  - DMGT_1997_17_1_a6
ER  - 
%0 Journal Article
%A Bucko, Jozef
%A Frick, Marietjie
%A Mihók, Peter
%A Vasky, Roman
%T Uniquely partitionable graphs
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 103-113
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a6/
%G en
%F DMGT_1997_17_1_a6
Bucko, Jozef; Frick, Marietjie; Mihók, Peter; Vasky, Roman. Uniquely partitionable graphs. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 103-113. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a6/