On the number of heterochromatic trees in nice and beautiful colourings of complete graphs

2021/06/05 by Montellano-Ballesteros, Juan José, Rivera-Campo, Eduardo, Strausz, Ricardo
#05C05 #05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.02905

Abstract

We introduce classes of edge-colourings of the complete graph -- that we call nice and beautiful -- and study how many heterochromatic spanning trees appear under such colourings. We prove that if the colouring is nice, there is at least a quadratic number of different heterochromatic trees; and if the colouring is beautiful there is an exponential number of different such trees.

Related

• Partitioning complete graphs by heterochromatic trees
• Rainbow spanning trees in properly coloured complete graphs
• Repeated patterns in proper colourings
• A note on total and list edge-colouring of graphs of tree-width 3
• Decompositions into isomorphic rainbow spanning trees