paper

Long heterochromatic paths in heterochromatic triangle free graphs

arXiv:0804.4526

Abstract

In this paper, graphs under consideration are always edge-colored. We consider long heterochromatic paths in heterochromatic triangle free graphs. 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 $k$ -good colorings, i.e., minimum color degree at least $k$ . For the heterochromatic triangle free graphs $K_{n}$ , we obtain that for every vertex $v \in V (K_{n})$ , $K_{n}$ has a heterochromatic $v$ -path of length at least $d^{c} (v)$ ; whereas for the heterochromatic triangle free graphs $G$ we show that if, for any vertex $v \in V (G)$ , $d^{c} (v) \geq k \geq 6$ , then $G$ a heterochromatic path of length at least $\frac{3 k}{4}$ .

12 pages