tailieunhanh - Báo cáo toán học: " Long heterochromatic paths in edge-colored graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Long heterochromatic paths in edge-colored graphs. | Long heterochromatic paths in edge-colored graphs He Chen and Xueliang Li Center for Combinatorics and LPMC Nankai University Tianjin 300071 . China lxl@ Submitted Jan 12 2005 Accepted Jun 10 2005 Published Jul 29 2005 AMS Subject Classification 2000 05C38 05C15 Abstract Let G be an edge-colored graph. A heterochromatic path of G is such a path in which no two edges have the same color. dc v denotes the color degree of a vertex v of G. In a previous paper we showed that if dc v k for every vertex v of G then G has a heterochromatic path of length at least p 1 1. It is easy to see that if k 1 2 G has a heterochromatic path of length at least k. Saito conjectured that under the color degree condition G has a heterochromatic path of length at least p2k 1 1. Even if this is true no one knows if it is a best possible lower bound. Although we cannot prove Saito s conjecture we can show in this paper that if 3 k 7 G has a heterochromatic path of length at least k 1 and if k 8 G has a heterochromatic path of length at least p3k 1 1. Actually we can show that for 1 k 5 any graph G under the color degree condition has a heterochromatic path of length at least k with only one exceptional graph K4 for k 3 one exceptional graph for k 4 and three exceptional graphs for k 5 for which G has a heterochromatic path of length at least k 1. Our experience suggests us to conjecture that under the color degree condition G has a heterochromatic path of length at least k 1. 1. Introduction We use Bondy and Murty 3 for terminology and notations not defined here and consider simple graphs only. Let G V E be a graph. By an edge-coloring of G we will mean a function C E N the set of nonnegative integers. If G is assigned such a coloring then we say that G is an edge-colored graph. Denote the colored graph by G C and call C e the color of the THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R33 1 edge e 2 E and C uv 0 if uv 2 E G for any u v 2 V G . All edges with the same color