Graph decompositions without isolated vertices (Q1892833)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Graph decompositions without isolated vertices |
scientific article; zbMATH DE number 767682
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Graph decompositions without isolated vertices |
scientific article; zbMATH DE number 767682 |
Statements
Graph decompositions without isolated vertices (English)
0 references
2 July 1995
0 references
The author proves the following conjecture of \textit{A. Frank} (Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975): Let \(G\) be a connected simple graph of order \(n\), and \(n= n_1+\cdots+ n_k\) be a partition of \(n\) with \(n\geq 2\). Suppose that the minimum degree of \(G\) is at least \(k\). Then the vertex set \(V(G)\) can be decomposed into disjoint subsets \(V_1,\dots, V_k\) so that \(|V_i|= n_i\) and the subgraph induced by \(V_i\) contains no isolated vertices for all \(i\), \(1\leq i\leq k\).
0 references
graph decompositions
0 references
partition
0 references
isolated vertices
0 references