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

A Conjecture on Edge Coloring of Graphs

作　　者：林育青[1] LIN Yuqing(Shantou Polytechnic,Shantou Guangdong 515078,China)

机构地区：[1]汕头职业技术学院,广东汕头515041

出　　处：《新疆大学学报（自然科学版）》2020年第3期255-259,265,共6页Journal of Xinjiang University(Natural Science Edition)

基　　金：2018年汕头职业技术学院重点科研课题(SZK2018Z01)。

摘　　要：若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.

关 键 词：边色数 正常的k边着色 正则图 

分 类 号：O157.5[理学—数学]