Graph decompositions without isolated vertices (Q1892833)

From MaRDI portal





scientific article; zbMATH DE number 767682
Language Label Description Also known as
default for all languages
No label defined
    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