Long heterochromatic paths in edge-colored graphs (Q2571276)

For a vertex \(v\) of an edge-coloured graph \(G\), the colour neighborhood CN\((v)\) of \(v\) is the set \(\{C(e)\mid e\) is incident with \(v\}\) and the colour degree \(d(v)=| \text{CN}(v)|\), where \(C(e)\) is the colour of the edge \(e\). A path is called heterochromatic if any two edges of it get different colours. In the following we suppose that \(d(v)=k\) for every vertex \(v\) of \(G\). The authors show if \(3\leq k\leq 7\), then \(G\) has a heterochromatic path of length at least \(k-1\), and if \(k\geq 8\), then \(G\) has a heterochromatic path of length at least \(\lceil 3k/5\rceil+1\). The following conjecture is given. For every integer \(k\geq 3\) there is in \(G\) a heterochromatic path of length at least \(k-1\).