Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Paul Horn

Harvard University

Rainbow spanning trees in complete graphs

Abstract:

A subgraph of an edge colored graph is called rainbow if each edge has a distinct color. Brualdi and Hollingsworth proved that in any edge coloring of a complete graph by perfect matchings, there are two edge disjoint rainbow spanning trees and conjectured that a full partition into rainbow spanning trees is possible (for $K_{2n}$ , where $n ? 3$). Kaneko, Kano, and Suzuki proved that one may always find three edge disjoint rainbow spanning trees. In this talk, we show that in this situation a constant fraction of the graph can be covered by edge disjoint rainbow spanning trees. We'll discuss some of the main challenges and ideas in the proof, and an extension of the conjecture by Kaneko, Kano, and Suzuki that considers all proper edge colorings and not just those by perfect matchings.

Host: Fan Chung Graham

May 9, 2013

4:00 PM

AP&M 7321

****************************