-
题名关于图的边着色的一个猜想
被引量：2
- 1
-
-
作者
林育青
-
机构
汕头职业技术学院
-
出处
《新疆大学学报（自然科学版）》
CAS
2020年第3期255-259,265,共6页
-
基金
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;此猜想也是成立的.
-
关键词
边色数
正常的k边着色
正则图
-
Keywords
edge chromatic number
normal k-edge coloring
regular graph
-
分类号
O157.5
[理学—数学]
-
-
题名边临界图
- 2
-
-
作者
林育青
-
机构
汕头职业技术学院自然科学系
-
出处
《南方职业教育学刊》
2011年第3期84-89,共6页
-
基金
汕头职业技术学院2009年科研立项课题"图的边着色猜想及广义图的着色研究"(SZK09B14)
-
文摘
本文定义了边临界图,并对其进行了研究,主要得到了以下性质:1)若G是△(G)边临界图,则G必为星图S△(G);2)若G是△(G)+1边临界图,则G没有割边;3)若G是△(G)+1边临界图,则对任意边uv,有d(u)+d(v)≥△(G)+2;4)若G是△(G)=3的简单连通图,且ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=χ/(G)=△(G)+1。此外,我们还提出猜想:"若G是简单图,G是△(G)+1边临界图,则ν(G)为奇数",并证明了此猜想与猜想"若G是简单图,ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=△(G)+1。"是等价的等结论。
-
关键词
边临界图
边色数
正常的k边着色
完美图
-
Keywords
Edge critical graph
Edge chromatic number
Proper k-edge colouring
Perfect graph
-
分类号
G4
[文化科学—教育学]
-
