Long heterochromatic paths in heterochromatic triangle free graphs

Abstract

In this paper, graphs under consideration are always edge-colored. We consider long heterochromatic paths in heterochromatic triangle free graph Two kinds of such graphs are considered, one is complete graphs with Gallai colorings, i.e., heterochromatic triangle free complete graphs; the other is heterochromatic triangle free graphs with κ;-good colorings, i.e., minimum color degree at least κ;. For the heterochromatic triangle free graphs Κ;_n, we obtain that for every vertex νε V(Κ;_n), Κ;_n has a heterochromatic ν-path of length at least d^c(ν); whereas for the heterochromatic triangle free graphs G we show that if, for any vertex νε; V(G), d ^c(ν) ≥k ≥6, then G has a heterochromatic path of length at least 3κ;/4.