单圈图和双圈图的连续边着色

摘要

设G是简单图,用颜色1,2,3, ...对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图G的亏度def(G)是粘在G上使得它可连续着色的悬挂边的最小数目.在本文中,我们完全确定了单圈图和双圈图的亏度.%Given a simple graph G, a proper edge-coloring of G with colors 1, 2, 3, ... is called consecutive if the colors represented at each vertex form an interval of integers. The deficiency def(G) of G is the minimum number of pendant edges whose attachment to G makes it consecutively colorable. In this paper, we completely determine the deficiency of unicyclic and bicyclic graphs.