若干图类的点可区别Ⅰ-全染色及Ⅵ-全染色

作     者：张生桂 

作者单位：西北师范大学 

学位级别：硕士

导师姓名：陈祥恩

授予年度：2021年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：图的联 Ⅰ-(Ⅵ-)全染色 点可区别Ⅰ-(Ⅵ-)全染色 点可区别Ⅰ-(Ⅵ-)全色数 

摘      要：设f为图G的一个一般全染色(即若干种颜色对图G的全部顶点及边的一个分配),如果(?)u,v∈V(G)且u,v相邻,就有f(u)≠f(v)并且(?)e1,e2∈ E(G)且e1,e2相邻,就有f(e1)≠f(e2),则称f为图G的Ⅰ-全染色;如果Ve1,e2∈E(G)且e1,e2相邻,就有f(e1)≠f(e2),则称f为图G的Ⅵ-全染色.令C(u)={f(u)}∪{f(uv)|uv∈E(G)}是u的色集合(非多重集).对图G的一个Ⅰ-全染色(分别地,Ⅵ-全染色)f,一旦(?)u,v ∈V(G),u≠u,就有C(u)≠C(v),则f称为图G的点可区别的Ⅰ-全染色(或点可区别Ⅵ-全染色),简称为VDIT染色(分别地,VDVIT染色).令χvt i(G)=min{k|G存在k-VDIT染色}.称χvt i(G)为图G的点可区别Ⅰ-全色数.令χvt vi(G)=min{k|G存在k-VDVIT染色}.称χvt vi(G)为图G的点可区别Ⅵ-全色数.在本文主要利用构造具体染色的方法,构造了联图mCs∨nCs(s为奇数),mC2t∨nC2t(t≥2),mC3∨Fn,mC3∨S2n,mC3∨Wn,mC4∨Fn,mC4∨S2n和mC4∨Wn的点可区别Ⅰ-全染色和点可区别Ⅵ-全染色;同时利用分析法和反证法讨论了最小度是n-2以及n-3的n阶图的点可区别Ⅰ-全染色和点可区别Ⅵ-全染色.从而确定了这些图的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数,最终证明了VDITC猜想和VDVITC猜想对于这些图是成立的.