ausblenden:
Schlagwörter:
Mathematics, Combinatorics, math.CO,
Zusammenfassung:
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)$.
