---
abstract: |
    In a properly edge colored graph, a subgraph using every color at most once is called *rainbow*. In this thesis, we study rainbow cycles and paths in proper edge colorings of complete graphs, and we prove that in every proper edge coloring of $K_n$, there is a rainbow path on $(3/4-o(1))n$ vertices, improving on the previously best bound of $(2n+1)/3$ from [@GyarfasMhalla2010].

    Similarly, a $k$-rainbow path in a proper edge coloring of $K_n$ is a path using no color more than $k$ times. We prove that in every proper edge coloring of $K_n$, there is a $k$-rainbow path on $(1-2/(k+1)!)n$ vertices.
author:
- Frank Mousset
bibliography:
- 'refs.bib'
date: 'August 22, 2011'
title: Rainbow Cycles and Paths
---

[thesistype[Bachelor Thesis]{}]{} [advisors[Advisors: Prof. Dr. Emo Welzl, Heidi Gebauer]{}]{} [department[Department of Computer Science]{}]{}

[-]{}

Introduction
============

Rainbow cycles and paths
------------------------

Consider an edge colored graph $G$. A subgraph of $G$ is called *rainbow* (or *heterochromatic*) if no two of its edges receive the same color. We are concerned with rainbow paths and, to a lesser extent, cycles in proper edge colorings of the complete graph $K_n$. Hahn conjectured that every proper edge coloring of $K_n$ admits a Hamiltonian 