论文部分内容阅读
如果图G的正常边染色不包含2-色圈,则称它是图G的无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ（G）＋2,其中Δ（G）为图G的最大顶点度。已经证明了当Δ≤3时,此猜想成立。本研究利用线性-时间算法思想研究了最大顶点度为4的图,并给出了最大顶点度为4的图G满足此猜想的一个充分条件为图G的任意2个最大度顶点都不邻接。