PROPERLY COLORED HAMILTONIAN PATHS IN EDGE-COLORED COMPLETE GRAPHS

We consider edge-coloured complete graphs. A path or cycle Q is called properly coloured (PC) if any two adjacent edges of Q differ in colou r. Our note is inspired by the following conjecture by B. Bollobas and P. Erdos (1976): if G is an edge-coloured complete graph on n vertice s in which the maximum monochromatic degree of every vertex is less th an right perpendicularn/2left perpendicular, then G contains a PC Hami ltonian cycle. We prove that if an edge-coloured complete graph contai ns a PC 2-factor then it has a PC Hamiltonian path. R. Haggekvist (199 6) announced that every edge-coloured complete graph satisfying Bollob as-Erdos condition contains a PC 2-factor. These two results imply tha t every edge-coloured complete graph satisfying Bollobas-Erdos conditi on has a PC Hamiltonian path. (C) 1998 Elsevier Science B.V. All right s reserved.