完全图中的正常染色的路和圈(英文)  

Properly Colored Paths and Cycles in Complete Graphs

作　　者：王光辉[1] 周珊[2] 

机构地区：[1]山东大学数学学院,济南250100 [2]兰州大学数学与统计学院,兰州730000

出　　处：《运筹学学报》2011年第3期51-56,共6页Operations Research Transactions

基　　金：National Natural Science Foundation of China(61070230,11026184,11101243);Independent Innovation Foundation of Shandong University(2009hw001);Research Fund for the Doctoral Program of Higher Education of China(20100131120017);the Scientific Research Foundation for the Returned Overseas Chinese Scholars

摘　　要：令K_n^c表示n个顶点的边染色完全图.令△^(mon)(K_n^c)表示K_n^c的顶点上关联的同种颜色的边的最大数目.如果K_n^c中的一个圈(路)上相邻的边染不同颜色,则称它为正常染色的.B.Bollobas和P.Erd(o|¨)s(1976)提出了如下猜想:若△^(mon)(K_n^c)<[n/2],则K_n^c中含有一个正常染色的Hamilton圈.这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈.Let Kn^c denote a complete graph on n vertices whose edges are colored in an arbitrary way. Let △^mon（Kn^c） denote the maximum number of edges of the same color incident with a vertex of Kn^c A properly colored cycle （path） in Kn^c is a cycle （path） in which adjacent edges have distinct colors. B. Bollobels and P. ErdSs （1976） proposed the following conjecture： If △^mon（Kn^c） 〈 [n/2J, then Kn^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.

关 键 词：正常染色圈 完全图 

分 类 号：O157.5[理学—数学]