特殊图类的非正常染色

设k,l是非负整数,图G的一个非正常(k, l)-染色是指用红蓝2种颜色对顶点集V(G)进行着色,使得对每一个染以红色(或蓝色)的点,至多k (或l)个邻点与其染色相同。本文主要研究路和圈的平方图的非正常(k, l)-染色。

平面图的非正常染色

研究了特殊平面图的非正常染色问题.应用经典的权转移方法,证明了4-圈不与3-,4-圈相邻且不含7-圈的平面图是(1,1,0)-可染的.这一结果进一步拓展了平面图的非正常可染的充分条件.

平面图不含短圈及相邻三角形的非正常染色

设d_1,d_2,…,d_k是k个非负整数。若图G=(V,E)的顶点集V能被分成k个子集V_1,V_2,…,V_k,使得对任意的i=1,2,…,k,Vi的点导出子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,…,d_k)-可染的。证明不含相邻三角形及i-圈的平面图是(2,0,0)-可染的,i=5,6。

信道分配与二部图的非正常边染色

确定二部图的边染色数和极小边染色是计算机领域的一个经典算法问题.该问题在信道分配和计算机科学的众多方面有广泛应用,并且是NP完全的.本文首先从二部图结构入手,利用非正常边染色定义,采用构造方法得到亏格为1和2时部分完全二部图的非正常边染色数,给出相应算法和复杂性分析,然后将其转化为网络中的信道数量.

图的无圈非正常列表染色

研究图的无圈非正常列表染色是当前图论领域的热点与难点问题.通过对极小反例G的结构分析,利用色延拓和色置换等方法证明了:最大度为4的非4-正则图是无圈(3,3)^*-可选的.所得结果推广了无圈非正常列表染色的若干结论.

既不含4-圈又不含6-圈的平面图的非正常染色

设d1,d2,...,dk是k个非负整数.若图G=(V,E)的顶点集V能被剖分成k个子集V1,V2,...,Vk,使得对任意的i=1,2,...,k,Vi的点导出子图G[Vi]的最大度至多为di,则称图G是(d1,d2,...,dk)-可染的.本文证明既不含4-圈又不含6-圈的平面图是(3,0,0)-和(1,1,0)-可染的.

图C_m^2×P_n与C_m^2×C_n的邻点可区别非正常边染色

设简单图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的邻点可区别边非正常边染色,并给出了相应色数.

不含4-圈和5-圈的平面图的非正常2-染色的一个新结果

设d_1,d_2,···,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V_1,V_2,···,V_k,使得对任意的i=1,···,k,V_i的点导出子图G[Vi]的最大度至多为di,则称图G是(d_1,d_2,···,d_k)-可染的,本文证明了既不含4-圈又不含5-圈的平面图是(9,9)-可染的.

广义Mycielski图M_n(P_m^2)的邻点可区别的非正常全染色

文中讨论了广义Mycielski图M_n(P_m^2)的邻点可区别非正常全染色,并给出了相应色数.

三正则构造图的邻点全和可区别全染色

首先,根据Snark图的结构特点,构造基于双星和十字交叉形的两类三正则图;其次,利用穷染法和组合分析法研究四类三正则构造图的邻点全和可区别全染色问题,得到了它们的邻点全和可区别全色数均为2.

关于图论课程教学中对染色问题的研究

图论起源于著名的哥尼斯堡七桥问题,是离散数学的重要分支。它在计算科学、社会科学和自然科学等多个领域都有广泛应用。本文主要研究广义Petersen图的非正常点染色问题,构造满足条件的染色方式。旨在帮助学生更好地理解图论基本概念,掌握图论中的基本技巧方法,从而培养学生科学解决问题的能力。

图C_m^2×S_n与C_m^2×F_n与的gndt-染色

单图G的邻点可区别的非正常全染色是指图的任意相邻两顶点的色集合都不同的全染色.所谓顶点的色集合是指顶点自身的颜色及与其关联的所有边的颜色的集合.文中讨论了笛卡儿积图C_m^2×S_n和C_m^2×F_n的邻点可区别非正常全染色,并给出了相应色数.

平方图的邻点全和可区别全染色

进一步研究了平方图的邻点全和可区别非正常全染色问题:利用平方图的结构构造了路、圈、毛毛虫、广义星以及最大度为3且不含2度点的树的平方图,通过组合分析法得到上述5类平方图的邻点全和可区别非正常全色数。

两类正则图的邻点全和可区别全染色

设f:V(G)∪E(G)→[1,k]是图G的一个非正常k-全染色.令φ(x)=f(x)+∑e∈xf(e)+∑y∈N(x)f(y),其中N(x)={y∈V(G)|xy∈E(G)}.对任意的边uv∈E(G),如果有φ(u)≠φ(v)成立,则称f是图G的一个邻点全和可区别(简记NFSD)k-全染色.图G的邻点全和可区别全染色中最小的k值称为G的邻点全和可区别全色数,记为fgndi_(Σ)(G).通过构造染色函数法,确定了广义Petersen图和循环图的邻点全和可区别全色数.

几类笛卡尔乘积图的邻点全和可区别全染色

设f:V(G)∪E(G)→[k]是图G的一个非正常的k-全染色,令权重(x)=f(x)+∑x∈ef(e)+∑y∈N(x)f(y),其中,N(x)={y∈V(G)|xy∈E(G)}对任意的边uv∈E(G),如果有(u)≠(v)成立,则称f为图G的一个邻点全和可区别非正常k-全染色。图G的邻点全和可区别非正常全染色中最少的颜色数k叫做G的邻点全和可区别全色数,记为fgndi∑(G)。文章研究了几类笛卡尔乘积图G×H的邻点全和可区别非正常全染色,得到fgndi∑(Pm×Pn)=fgndi∑(Pm×Cn)=fgndi∑(Cm×Cn)=fgndi∑(Pm×Kn)=fgndi∑(Cm×Kn)=2。结果表明,邻点全和可区别全染色猜想对上述几类笛卡尔乘积图均成立。

森林的非正常均匀染色

给出了森林是均匀(k,d)*-可染的一个充要条件,推广了Gerard J.Chang关于森林的均匀染色的充要条件。

欧拉公式的一个应用

对于图G的所有顶点v∈V(G)的每个满足|L(v)|=m的列表分配L,如果G总存在一个L-染色,使得G的每个顶点至多有d个邻点与它自己染相同的颜色,则称图G是d-缺陷m-可选的。Ko-wei Lih等结合欧拉公式用放电的方法证明了每个不含4-圈和i-圈的平面图是1-缺陷3-可选的,其中i∈|5,6,7|。对于2-连通图,只用欧拉公式就能证明他们的结果。

不含相交3圈和相邻4^-圈的平面图是(2,2,0)-可染的

设c1,c2,…,ck是k个非负整数.若图G=(V,E)的顶点集V能被剖分成k个子集V1,V2,…,Vk,使得对任意的i=1,2,…,k,顶点Vi的导出子图G[Vi]的最大度至多为ci,则称图G是(c1,c2,…,ck)-可染的.本文证明既不含相交3-圈又不含相邻4—-圈的平面图是(2,2,0)-可染的.

不含相邻短圈的平面图的 (3, 1)*-可选性

图 G的一个颜色列表配置 L是指给 G中的每个顶点 v都分配一个可用色集 L(v)。 如果在映射 ?下对任意 v ∈ V (G)均满足 ?(v) ∈ L(v),使得在 v的邻点中至多有 d个顶点的颜色为 ?(v),那 么我们称 G是 (L, d)?-可染的。 如果对任意颜色列表配置 L = {L(v)||L(v)| ≥ k, v ∈ V (G)}, G都 是 (L, d)?-可染的,那么我们就称 G 是 (k, d)?-可选的。 Xu 和Zhang 猜想:不含相邻 3-圈的平 面图是 (3, 1)?-可选的。 在本文中,我们将证明不含相邻 k-圈的平面图是 (3, 1)?-可选的,其中k ∈ {3, 4, 5}。

关于图的邻和可区别全染色的新方法

给出树的邻和可区别2-全染色方案,并结合三正则图最小消圈集的独立性以及消圈子图的无圈性,较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。