### Abstract

We show that in any edge-coloring of the complete graph K_{n} on n vertices, such that each color class forms a complete bipartite graph, there is a spanning tree of K_{n}, 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 language | English (US) |
---|---|

Pages (from-to) | 143-148 |

Number of pages | 6 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 53 |

Issue number | 1 |

DOIs | |

State | Published - Sep 1991 |

Externally published | Yes |

### 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

Alon, N., Brualdi, R. A., & Shader, B. L. (1991). Multicolored forests in bipartite decompositions of graphs.

*Journal of Combinatorial Theory, Series B*,*53*(1), 143-148. https://doi.org/10.1016/0095-8956(91)90059-S