p_1-类图的双约束边色数

Double Edge Chromatic Number of p_1-Graphs

双约束边染色是指对平面图G的边进行染色,使得相邻的边染不同的颜色且在同一个面上的边也有不同的颜色。图G的双约束边色数eχ/vf(G)是指对图G进行双约束边染色所需要的最少的颜色数,各种平面图的双约束边色数的上界是研究双约束边染色的焦点问题。证明了对于高度平面图中的p1-类图,恒有eχ/vf(G)≤Δ(G)+1成立,其中Δ(G)为图G的最大度。

The double - edge coloring is defined as coloring the edges of G such that arbitrary adjacent edges are assigned with distinct colors and the edges in the boundary of a face are also assigned with distinct colors. The double-edge chromatic number,Xe/vf （G） ,is the smallest number of colors such that G admits a double edge coloring, and the upper bound of the double - edge chromatic number for all kinds of planar graphs is the focus for studying the double edge coloring. The main result of this paper is to give an upper bound,△（G）＋1, for P1 - graph, the special plane graph with high maximum degree.