论文部分内容阅读
双约束边染色是指对平面图G的边进行染色，使得相邻的边染不同的颜色且在同一个面上的边也有不同的颜色。图G的双约束边色数Xe/vf（G）是指对图G进行双约束边染色所需要的最少的颜色数，各种平面图的双约束边色数的上界是研究双约束边染色的焦点问题。证明了对于高度平面图中的p1-类图，恒有Xe/vf（G）≤△（G）＋1成立，其中△（G）为图G的最大度。