Long properly colored cycles in edge colored complete graphs
Long properly colored cycles in edge colored complete graphs
复制标题
DOI：
10.1016/j.disc.2014.02.003
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
G. Wang;Tao-Ming Wang;G. Liu
中科院分区：
文献类型：
--
作者：
G. Wang;Tao-Ming Wang;G. Liu
设Knc表示n个顶点的完全图，其边可以任意着色.设Δ mon（Knc）表示与Knc中的一个顶点相关联的同色边的最大数目.在K n c中，一个适当着色的圈（路径）是指相邻边具有不同颜色的圈（路径）。B。Bollobás和P. Erdös（1976）提出了如下猜想：如果Δ mon（Knc）<n2，则Knc包含一个适当着色的Hamilton圈。Li，Wang和Zhou证明了：如果Δ mon（Knc）<<$n2 <$$>，则Knc包含一个长度至少为<$n+23 <$n + 1的真色圈.本文将这一界改进为n = 2n + 2.
Let K n c denote a complete graph on n vertices whose edges are colored in an arbitrary way. Let Δ mon (K n c) denote the maximum number of edges of the same color incident with a vertex of K n c. A properly colored cycle (path) in K n c 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 (K n c)<⌊ n 2⌋, then K n c contains a properly colored Hamiltonian cycle. Li, Wang and Zhou proved that if Δ mon (K n c)<⌊ n 2⌋, then K n c contains a properly colored cycle of length at least⌈ n+ 2 3⌉+ 1. In this paper, we improve the bound to⌈ n 2⌉+ 2.