Almost all trees have tribe number 2 or 3
type: Item
instance of: scholarly article
title: Almost all trees have tribe number 2 or 3
zbMATH Open document ID: 0828.05024
DOI: 10.1016/0012-365X(93)E0013-T
author: János Komlós
author: W. O. J. Moser
published in: Discrete Mathematics
publication date: 1995-08-27T00:00:00Z
review text: For a fixed \(\varepsilon\leq 1/2\), the tribe number \(t_T(\varepsilon)\) of \(T\) is defined as the smallest integer \(r\), such that for every vertex \(v\) in \(T\), the forest obtained from deleting \(v\) from \(T\) contains a collection of at most \(r\) trees that contain together more than \((1- \varepsilon)n\) vertices (\(n\) denoting the number of vertices of \(T\)). The tribe number of a tree can be arbitrarily large. However, as is shown in this paper, almost every tree has tribe number 2 or 3 (with respect to any fixed \(\varepsilon\leq 1/2\)).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 790561
zbMATH Keywords: tribe number
zbMATH Keywords: forest
zbMATH Keywords: tree
reviewed by: Hans L. Bodlaender
Wikidata QID: Q115927660
MaRDI profile type: Publication
full work available at URL: 0012-365x(93)e0013-t
OpenAlex ID: W1998185014
description: scientific article; zbMATH DE number 790561