Graph decompositions without isolated vertices. II
type: Item
instance of: scholarly article
title: Graph decompositions without isolated vertices. II
zbMATH Open document ID: 0907.05041
author: Hikoe Enomoto
author: Shinsuke Matsunaga
published in: Journal of the Mathematical Society of Japan
publication date: 1999-02-11T00:00:00Z
review text: The following result is proven: Let \(G\) be a connected, simple graph with \(| V(G) |= n= a_1+ a_2+ \cdots+ a_k\), \(a_i \geq 2\). Then, there is a partition of the vertices of \(G\) into \(k\) subsets, \(A_1, A_2, \ldots , A_k\) with \(| A_i |= a_i\), so that for every vertex \(v \in V(G)\) of degree at least \(k\), if \(v \in A_i\), \(v\) has degree at least one in the subgraph induced by the vertices of \(A_i\). This generalises an earlier result of \textit{H. Enomoto} [J. Comb. Theory, Ser. B 63, No. 1, 111-124 (1995; Zbl 0834.05046)] and in doing so resolves a conjecture of Y. Egawa (unpublished).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1172188
zbMATH Keywords: graph decomposition
zbMATH Keywords: partition
zbMATH Keywords: induced subgraph
zbMATH Keywords: isolated vertices
reviewed by: Katherine Heinrich
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.2969/jmsj/04910161
OpenAlex ID: W1980878383
DOI: 10.2969/JMSJ/04910161
description: scientific article; zbMATH DE number 1172188