Multicolored forests in bipartite decompositions of graphs

Noga Alon, Richard A. Brualdi, Bryan L. Shader

Research output: Contribution to journalArticle

15 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)143-148
Number of pages6
JournalJournal of Combinatorial Theory, Series B
Volume53
Issue number1
DOIs
StatePublished - Sep 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Multicolored forests in bipartite decompositions of graphs'. Together they form a unique fingerprint.

  • Cite this