de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

#### On Induced Colourful Paths in Triangle-free Graphs

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44226

Chandran,  L. Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

arXiv:1604.06070.pdf
(Preprint), 146KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Babu, J., Basavaraju, M., Chandran, L. S., & Francis, M. C. (2016). On Induced Colourful Paths in Triangle-free Graphs. Retrieved from http://arxiv.org/abs/1604.06070.

Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is "colourful" if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on $\chi(G)$ vertices. It is interesting to think of what analogous result one could obtain if one considers induced colourful paths instead of just colourful paths. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $\chi(G)$ vertices. As proving this conjecture in its fullest generality seems to be difficult, we study a special case of the conjecture. We show that the conjecture is true when the girth of $G$ is equal to $\chi(G)$. Even this special case of the conjecture does not seem to have an easy proof: our method involves a detailed analysis of a special kind of greedy colouring algorithm. This result settles the conjecture for every properly coloured triangle-free graph $G$ with girth at least $\chi(G)$.