The color-degree matrix and the number of multicolored trees in star decompositions
In a previous paper we investigated the problem of counting the number of multicolored spanning trees in biclique decompositions. In particular, for acyclic decompositions we found the minimum and maximum numbers of multicolored trees. We now introduce the color-degree matrix \(C\) and show that the number of multicolored trees is bounded below by the determinant of \(C\) with a row deleted. In fact, we get equality for acyclic decompositions and for star decompositions. Unfortunately, for arbitrary decompositions the ratio of this determinant to the actual number of trees can approach zero. We find that star decompositions on \(n\) vertices are in one to one correspondence with tournaments on \(n-1\) vertices. This allows us to determine that the minimum number of multicolored trees among all star decompositions of \(K_ n\) is \((n-1)\)! and the average number is \(((n+1)/2)^{n-2}\). We bound the maximum number of multicolored trees between this average and \(\lfloor n^ 2/4\rfloor^{(n-1)/2}-\lfloor(n-2)^ 2/4\rfloor^{(n-1)/2}\).
- scientific article; zbMATH DE number 139929
- scientific article; zbMATH DE number 7351424
- ON STAR COLORING OF DEGREE SPLITTING OF COMB PRODUCT GRAPHS
- Multicolored forests in bipartite decompositions of graphs
- Multichromatic numbers, star chromatic numbers and Kneser graphs
- Multicolored trees in complete graphs
- Multicolored trees in complete graphs
- On the degree-chromatic polynomial of a tree
- On the degree-chromatic polynomial of a tree
- scientific article; zbMATH DE number 1929966
This page was built for publication: The color-degree matrix and the number of multicolored trees in star decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322016)
