Every tree contains a large induced subgraph with all degrees odd
type: Item
instance of: scholarly article
title: Every tree contains a large induced subgraph with all degrees odd
zbMATH Open document ID: 0822.05022
DOI: 10.1016/0012-365X(93)E0186-8
published in: Discrete Mathematics
publication date: 1995-09-28T00:00:00Z
review text: It is proved that every tree of order \(n\) contains an induced subgraph of order at least \(2\lfloor(n+ 1)/ 3\rfloor\) with all degrees odd; and this bound is best possible.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 769319
zbMATH Keywords: tree
zbMATH Keywords: induced subgraph
zbMATH Keywords: bound
author: Andrew John Radcliffe
author: Alex Scott
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
cites work: Q4198785
cites work: On induced subgraphs with odd degrees
cites work: On induced subgraphs of trees, with restricted degrees
cites work: Q3880849
cites work: Large Induced Subgraphs with All Degrees Odd
full work available at URL: 0012-365x(93)e0186-8
OpenAlex ID: W2023006192
description: scientific article; zbMATH DE number 769319