Enumeration of equicolorable trees
type: Item
instance of: scholarly article
zbMATH Open document ID: 0966.05018
DOI: 10.1137/S0895480100368463
published in: SIAM Journal on Discrete Mathematics
publication date: 2001-03-19T00:00:00Z
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1578824
zbMATH Keywords: generating functions
zbMATH Keywords: asymptotic enumeration
zbMATH Keywords: tree
author: Nicholas Pippenger
MaRDI profile type: Publication
Recommended article: Q3331245
Recommended article: Equitable coloring of trees
Recommended article: THE COLORING OF THE TREE OF COLORINGS
Recommended article: Tree-chromatic number
Recommended article: Enumeration of (uni- or bicolored) plane trees according to their degree distribution
Recommended article: Nonrepetitive colorings of trees
Recommended article: Q4361560
Recommended article: Enumeration problems of trees
Recommended article: A note on trees colouring
Recommended article: Q3305348
title: Enumeration of equicolorable trees
review text: The author defines a tree to be equicolorable if a proper bicoloring of its vertices assigns the two colors to equal numbers of vertices. It is not difficult to show that the probability that a randomly chosen (rooted or unrooted) \(n\)-vertex labelled tree is equicolorable is asymptotic to two times the probability that its vertices would be equicolored if they were assigned colors by independent coin flips. The author shows that for a randomly chosen (rooted or unrooted) \(n\)-vertex unlabelled tree the corresponding statements holds when two is replaced by \(1.40499\dots\)\ .
reviewed by: J. W. Moon
description: scientific article