一类特殊图的顶点染色及其猜想的证明

通过研究一类特殊图的顶点染色,得到了以下结果:给出了S=p-3且p∈{4,5,6},图G的顶点染色数;证明了︱S︱p2且︱S︱=p-3的图G不存在第p-m类图,m≥7且m是正整数;证明了︱S︱=p-3时,χ(G)≤4θ(G)+θ2(G)-1;进一步证明了猜想χ(G)≤4θ(G)+θ2(G)-1是正确的;为今后研究该猜想和图的顶点染色提供一些思想方法.     

含相邻三角形的平面图的列表边和列表全染色

给定一个平面图G,χ´_l(G)和χ"_l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´_l(G)≤Δ(G)+1和χ"_l(G)≤Δ(G)+2成立。     

合成图的点可区别正常边色数

通过将图G和H的合成图G［H］分解成一个直积图G□H和一个二分图Z的边不交并的方法, 得到了χ′_s(G［H］)≤χ′_s(G□H)+χ′(Z),其中χ′_s(G)表示G的点可区别正常边色数.     

图的点可区别IE-全色数的一个上界

用概率方法研究图的点可区别IE-全色数的一个上界,得到:如果δ≥7且16Δ≤n≤Δ⁷/[32×10⁵(Δ+1)] +1, 则χ^ie_vt(G)≤16Δ ,这里n是G的阶,δ是G中点的最小度数,Δ是G中点的最大度数。       

Schrijver图S_G(2k+2,k)的全色数

图G的一个k-全染色是用k种颜色对图G的顶点和边进行染色,使得任意相邻的边、相邻的顶点和相关联的顶点和边都染不同的颜色.图G的全色数是图G的k-全染色中最小的k值,记为χ″(G).Behzad和Vizing分别独立地提出了著名的全染色猜想TCC:Δ+1≤χ″(G)≤Δ+2,Δ表示图G的最大度.研究了Schrijver图SG(2k+2,k)的全色数问题,得到了χ″(SG(2k+2,k))=Δ+1=k+3,其中k≥2.     

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图，其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖，如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ，由此将 χ’c(G)=δ的图称为CⅠ类图，否则称为CⅡ类图. 显然，图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的。     

色数与谱半径和生成偶子图

设G为n≥1 阶简单无向图,ρ(G)和μ(G)分别表示图G的邻接谱谱半径和Laplacian谱谱半径.利用生成偶子图证明了：当k为偶数时,ρ(G)≤（k-1）/kμ(G);当k为奇数时,ρ(G)≤k/（k+1）μ(G).其中k(≥1)为简单图G的色数.     

一类平面图的强边染色

图G的强边染色是指对图G的边进行染色,使得距离不超过2的任意两条边染不同的颜色. 任何一个平面图都可用4Δ+4种颜色进行强边染色. 证明了当平面图没有k-圈(4≤k≤10)且3-圈不相交时(即每个顶点至多关联一个3-圈), 必定存在一个3Δ+1种颜色的强边染色.     

完全二部图K_(4,n)(n≥47)的点可区别E-全染色

G是一个简单图,G的一个E-全染色f是指使相邻顶点着不同颜色且每条关联边与它的顶点着以不同颜色的全染色。设f为G的一个E-全染色,对任意x∈V(G),用C(x)表示在f下顶点的颜色以及与x关联的边的颜色所构成的集合。若任意u,v∈V(G),u≠v,有C(u)≠C(v),则称f是图G的点可区别的E-全染色,简称VDET染色。图G的VDET染色所用颜色数目的最小值称为图G的的点可区别E-全色数或简称VDET色数,记为χ_vt~e(G)。讨论并给出了完全二部图K_(4,n)(n≥47)的点可区别E-全色数。     

图的子图中(n,r)-正交因子分解

设图G的顶点集为V(G)，边集为E(G)，g和f是定义在V(G)上的2个整值函数，满足对于一切x∈V(G)，g(x)≤f(x).若G是一个(mg+rn，mf-rn)-图，1≤n＜m，r≥2，且对于x∈V(G)，有g(x)≥k≥1，则存在G的一个子图G′，使得G′具有一个(f，g)-因子(n，r)-正交于G的任意给定子图H，其中｜E(H)｜=nk.     

完全二部图K_(3,n)(3≤n≤17)的点可区别E-全染色

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.     

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

关于非平面图染色的一个猜想

本文提出以下猜想:若θ(G)=2,则χ(G)≤9;若θ(G)≥3,则χ(G)≤6θ(G)-1。证明了当 |S|∈{p,p-1,p-2,p-3,p-4,p-5}时,该猜想是正确的。     

完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色

考虑完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色.利用组合分析法、反证法及构造染色的方法,给出一类特殊完全二部图的点可区别E-全染色.结果表明:当6≤n≤10时,K_(6,n)的点可区别E-全色数为5;当11≤n≤38时,K_(6,n)的点可区别E-全色数为6.     

图的邻点可区分染色猜想成立的两个充分条件

简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}∪{f(uw)|uw∈E(G),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为χat(G)(χ′as(G)).图G的最大度记为Δ(G).本文给出了χat(G)=Δ(G)+3的一个充分条件和χ′as(G)=Δ(G)+2的一个充分条件.     

幂图的点强全色数

图G的一个正常全染色称为图G的点强全染色,当且仅当N[v]中任意元素都染有不同的颜色,其中N[v]={u}uu∈E（G）}U{u},图G的点强全染色所用颜色的最少数目称为图G的点强全色数．文章通过研究幂图t的结构性质,利用穷染、置换的方法,研究了幂图礴的点强全色数,并给出了一种具体的染色方案．     

W_m与P_n（n≤3）联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E（G）到{1,2,…,k}的映射,且满足u,v∈V（G）,u≠v,有S（u）≠S（v）,其中S（u）={f（uw）｜uw∈E（G）}.数min{k｜G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs′（G）,研究了Wm∨Pn（n≤3）的点可区别边染色,给出了Wm∨Pn（n≤3）的点可区别边色数.     

围长为4的无7-,8-圈和15-圈平面图的3-选色

图G的选色数(记为χ_l(G)), 定义为最小的自然数k, 满足当对任一顶点给定k种颜色的列表, 且染色时每个顶点的颜色只能从自身的颜色列表 中选择时, 存在图G顶点的一个正常着色. 应用Discharging方法对上述问题进行研究, 证明了每个围长至少为4且不含7-圈, 8-圈和15-圈的平面图是3-可选择的.