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

设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是一个简单图,其顶点集为V(G)而边集为E(G).图G的一个k-染色是指顶点集V(G)到色集{1,2,…,k}的一个映射.如果图G的一个点染色使G的每个极大团所有颜色均出现(这里不要求邻点染色不同),则称该染色为图G的全色极大团染色.而G的全色极大团色数是指能进行全色极大团染色的最大颜色数,记为χmaxcT(G).     

一类边覆盖临界图的构造

在图的边覆盖染色中边覆盖临界图的构造问题一直是研究的热点和难题.给出了一类边覆盖临界图的构造方法.对于任意给定的最小度δ,利用该方法可以构造出相应的一类边覆盖临界图.     

图的边覆盖数、围长和最大亏格

设G为图,用ω(G)和g(G)分别表示图G的边覆盖数和围长.结合图G的边覆盖数和围长等条件,得到了Betti亏数ξ(G)的一个上界,即设G为k-边连通图,则ξ(G)≤{|V(G)|-ω(G)(「)g(G)/2」, k=1,max{1,|V(G)|-ω(G)(k-1)(「)g(G)/2」-1},k=2,3.进而得到最大亏格γM(G)的一个下界.所得结果改进了目前已有的结果.     

若干倍图的Smarandachely邻点边染色

图G(V,E)的Smarandachely邻点边色数是满足条件uv∈E(G),|C(u)＼C(v)|≥1并且|C(v)＼C(u)|≥1的一个正常边染色的最小边色数,其中C(u)=｛f(uv)|uv∈E(G)｝。给出了路、圈、星、扇图的倍图的Smarandachely邻点边色数。     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

图C2m×Pn与C2m×Cn的邻点可区别非正常边染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.在这篇文章里,我们讨论了笛卡儿积图C2m×Pn和C2m×Cn的邻点可区别边非正常边染色,并给出了相应色数.     

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

简单连通图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的一个充分条件.     

完全二部图K_(9,n)的点可区别IE-全染色(英文)

G是一个简单图,G的一个IE全染色f是一个映射,该映射满足:对u,v∈V(G),u≠v,有C(u)≠C(v).图G的一个点可区别IE-全染色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)},简称k-VDIET.数min{k:G有一个k-VDIET染色}称为图G的点可区别IE-全色数或简称VDIET色数,记为χievt(G).本文讨论并给出了完全二部图K9,n的点可区别IE-全色数.     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

几类图的2-强边染色

研究了树、圈、完全二部图和轮图的2-强边染色问题.对于树,给出了2-强边色数等于最大顶点度加1的充分条件;对于圈、完全二部图及轮图,求出了2-强边色数,并给出了相应的染色方案.     

一些平面图的无圈边染色

主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。     

路与路联图的邻强边染色和均匀邻强边染色(英文)

对于图G的一个正常边染色c,如果相邻的点所关联的边集的色集不相等,c称为邻强边染色.图G的邻强边染色所需要的最小值称为图G的邻强边色数.如果每个色类所含的边数最多差一,c被称为均匀边染色,其最小值称为图G的均匀边色数.论文确定了路与路联图的邻强边染色数和均匀邻强边染色数.     

关于强边着色猜想的最优图问题

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.     

不含3,4圈的平面图的无圈边染色的一个结果

利用差值转移方法研究了不含3圈,4圈的平面图的无圈边染色,证得了它们的无圈边色数不超过Δ(G)+2。     

几类完全4-部图的邻强边染色

得到了几类完全4-部图的邻强边色数.     

不含4圈的平面图的无圈边色数的新上界

 为了研究平面图的无圈边染色,利用差值转移方法并结合平面图的结构性质,证明了不含4圈的平面图的无圈边色数不超过Δ(G)+6.     

边列表着色综述

图的边列表着色是一种正常边着色,它要求每条边的颜色在该边所给的列表中.本文对这一问题的研究进行了综述.