Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423395 | Discrete Mathematics | 2014 | 6 Pages |
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
Guanghui Wang, Tao Wang, Guizhen Liu,