Article ID Journal Published Year Pages File Type
6423395 Discrete Mathematics 2014 6 Pages PDF
Abstract

Let Knc denote a complete graph on n vertices whose edges are colored in an arbitrary way. Let Δmon(Knc) denote the maximum number of edges of the same color incident with a vertex of Knc. A properly colored cycle (path) in Knc is a cycle (path) in which adjacent edges have distinct colors. B. Bollobás and P. Erdös (1976) proposed the following conjecture: if Δmon(Knc)<⌊n2⌋, then Knc contains a properly colored Hamiltonian cycle. Li, Wang and Zhou proved that if Δmon(Knc)<⌊n2⌋, then Knc contains a properly colored cycle of length at least ⌈n+23⌉+1. In this paper, we improve the bound to ⌈n2⌉+2.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,