Enumeration of equicolorable trees

DOI10.1137/S0895480100368463MaRDI QIDQ2706191zbMATH OpenFDO

Authors Nicholas Pippenger

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480100368463

zbMATH Keywords

asymptotic enumerationgenerating functionstree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Trees (05C05) Enumeration in graph theory (05C30)

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\)\ .

Recommendations

• scientific article; zbMATH DE number 3863230
• Equitable coloring of trees
• THE COLORING OF THE TREE OF COLORINGS
• Tree-chromatic number
• Enumeration of (uni- or bicolored) plane trees according to their degree distribution
• Nonrepetitive colorings of trees
• scientific article; zbMATH DE number 1080074
• Enumeration problems of trees
• A note on trees colouring
• Enumeration on trees under relabelings

Cited in

(4)

• scientific article; zbMATH DE number 3863230 (Why is no real title available?)
• Broadcasting‐induced colorings of preferential attachment trees
• Existence and classification of b-contact structures
• Tree-chromatic number

This page was built for publication: Enumeration of equicolorable trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706191)