Abstract:

Properly colored paths and cycles in edge colored triangle-free graphs are discussed, and the known result is improved in triangle-free graphs. It is proved that in any edge colored triangle-free graph G with color degree at least d(d≥2), there exists either a properly colored path of size at least 4d-2, or a properly colored cycle of size at least 2「2d3.

Key words: edge colored graph; color degree; properly colored path; properly colored cycle