关于图的边着色的一个猜想

A Conjecture on Edge Coloring of Graphs

若G是简单图,v(G)是偶数,χ’(G)=△(G)+1,则存在点v∈V(G),使χ’(G-v)=χ’(G)=△(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ’(G)=△(G)+1;(2)设G是连通图,κ’(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k>2),v(G)=2n+2,χ’(G)=△(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ’(G)=△(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ’(G)=△(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)<d(u)<k外,其它顶点的度都等于k,χ’(G)=△(G)+1;此猜想也是成立的.

If G is a simple graph, and V(G)=2n, then there is a vertex v of G that makes χ’(G-v)=χ’(G)=△(G)+1. So far this conjecture has not been solved. In this paper, we have studied this and proved this conjecture is true when a graph satisfies one of the following conditions:(1) if G is a connected graph with cut edge;(2)if G is a connected graph, κ’(G)=2, except for two 2-degree vertices at most, the degrees of other vertices are k(k>2), and V(G)=2n+2;(3) if G is a K-regular graph, and V(G)=2n+2;(4) if G is a connected graph with V(G)=2n+2, and the degrees of other vertices are equal to k except a vertex v satisfies d(v)<k;(5) if G is a connected graph with V(G)=2n+2, and the degrees of other vertices are equal to k except two vertexs u and v which satisfy d(v)<d(u)<k.