About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Combinatorial Theory, Series B
Paper
Multicolored forests in bipartite decompositions of graphs
Abstract
We show that in any edge-coloring of the complete graph Kn on n vertices, such that each color class forms a complete bipartite graph, there is a spanning tree of Kn, no two of whose edges have the same color. This strengthens a theorem of Graham and Pollak and verifies a conjecture of de Caen. More generally we show that in any edge-coloring of a graph G with p positive and q negative eigenvalues, such that each color class forms a complete bipartite graph, there is a forest of at least max{p, q} edges, no two of which have the same color. In the case where G is bipartite there is always such a forest which is a matching. © 1991.