Graph decompositions without isolated vertices (Q1892833)

From MaRDI portal





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
    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

    Identifiers