10.3969/j.issn.1672-6987.2011.02.023
最大度为4的图的无圈边染色
如果图G的正常边染色不包含2-色圈,则称它是图G的无圈边染色.图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.2001年,Alon等猜想任意简单图G的无圈边色数都不超过△(G)+2,其中△(G)为图G的最大顶点度.已经证明了当△≤3时,此猜想成立.本研究利用线性-时间算法思想研究了最大顶点度为4的图,并给出了最大顶点度为4的图G满足此猜想的一个充分条件为图G的任意2个最大度顶点都不邻接.
图、无圈边染色、无圈边色数
32
O157.5(代数、数论、组合理论)
2011-08-15(万方平台首次上网日期,不代表论文的发表时间)
共4页
208-210,215