Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph GG. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of GG–the minimum number of distinct colors occurring at edges incident to any vertex of GG–denoted by ϑ(G)ϑ(G).Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph GG would be ⌈2ϑ(G)3⌉. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph GG is at least ϑ(G)−1ϑ(G)−1, if 1≤ϑ(G)≤71≤ϑ(G)≤7, and at least ⌈3ϑ(G)5⌉+1, if ϑ(G)≥8ϑ(G)≥8. They conjectured that the tight lower bound would be ϑ(G)−1ϑ(G)−1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if ϑ(G)≥8ϑ(G)≥8, then GG contains a heterochromatic path of length at least ⌈2ϑ(G)3⌉+1.In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if GG has no four cycles, then it contains a heterochromatic path of length at least ϑ(G)−o(ϑ(G))ϑ(G)−o(ϑ(G)) and if the girth of GG is at least 4log2(ϑ(G))+24log2(ϑ(G))+2, then it contains a heterochromatic path of length at least ϑ(G)−2ϑ(G)−2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of ⌊5ϑ(G)6⌋ and for bipartite graphs we obtain a lower bound of ⌈6ϑ(G)−37⌉.In this paper, it is also shown that if the coloring is such that GG has no heterochromatic triangles, then GG contains a heterochromatic path of length at least ⌊13ϑ(G)17⌋. This improves the previously known ⌈3ϑ(G)4⌉ bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph GG contains a heterochromatic path of length at least ⌈2ϑ(G)3⌉.