运筹学学报 ›› 2011, Vol. 15 ›› Issue (3): 51-56.

• 运筹学 • 上一篇    下一篇

完全图中的正常染色的路和圈

王光辉,周珊   

  • 出版日期:2011-09-20 发布日期:2011-09-20

Properly Colored Paths and Cycles in Complete Graphs

 WANG  Guang-Hui, ZHOU  Shan   

  • Online:2011-09-20 Published:2011-09-20

摘要: 令$K_{n}^{c}$表示$n$ 个顶点的边染色完全图.
令 $\Delta^{mon}
(K_{n}^{c})$表示$K^c_{n}$的顶点上关联的同种颜色的边的最大数目.
如果$K_{n}^{c}$中的一个圈(路)上相邻的边染不同颜色,则称它为正常染色的.
B. Bollob\'{a}s和P. Erd\"{o}s (1976) 提出了如下猜想:若 $\Delta^{{mon}}
(K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, 则$K_{n}^{c}$中含有一个正常染
色的Hamilton圈. 这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈.  

关键词: 正常染色圈, 完全图

Abstract: Let $K_{n}^{c}$ denote a complete graph on $n$ vertices whose edges are
colored in an arbitrary way. Let $\Delta^{mon}
(K_{n}^{c})$ denote the maximum number of edges of the same color incident with a vertex of $K^c_{n}$. A properly colored cycle (path) in $K_{n}^{c}$ is a
cycle (path) in which adjacent edges have distinct colors. B. Bollob\'{a}s and P. Erd\"{o}s (1976) proposed the following conjecture: If $\Delta^{{mon}}
(K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, then $K_{n}^{c}$ contains a properly colored
Hamiltonian cycle. This conjecture is still open. In this paper, we study properly colored paths and cycles under the condition mentioned in the above conjecture.  

Key words: properly colored cycle, complete graph