Graph decompositions without isolates
type: Item
instance of: scholarly article
title: Graph decompositions without isolates
zbMATH Open document ID: 0535.05052
DOI: 10.1016/0095-8956(84)90010-8
published in: Journal of Combinatorial Theory. Series B
publication date: 1984-01-01T00:00:00Z
review text: A. Frank conjectured that if \(G=(V,E)\) is a connected graph with minimal degree \(\geq k\) and \(a_ 1,...,a_ k\geq 2\) are integers with \(\sum a_ i=| V|\), then V may be decomposed into \(A_ 1,...,A_ k\), such that \(| A_ i| =a_ i\) and the subgraph induced by \(A_ i\) in G has no isolated vertices \((i=1,...,k)\). The case \(k=2\) has been proved by \textit{S. B. Maurer} [J. Comb. Theory, Ser. B 27, 294-319 (1979; Zbl 0413.05009)]. In this article the author proves the conjecture for \(k=3\) and for the case \(a_ 1=...=a_{k-1}=2\). Additionally he proves a related characterization of k-connected graphs which was independently proved by \textit{E. Györi} [Combinatorica 1, 263-273 (1981; Zbl 0494.05041)].
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3849280
zbMATH Keywords: minimum degree
zbMATH Keywords: induced subgraphs
zbMATH Keywords: isolated vertices
author: Nathan Linial
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: 0095-8956(84)90010-8
OpenAlex ID: W2025644987
cites work: Q3941433
cites work: Q3852212
cites work: Q4168622
cites work: A homology theory for spanning tress of a graph
cites work: Vertex colorings without isolates
description: scientific article; zbMATH DE number 3849280