近完全图的邻点可区别正常边色数

引入了近完全图的概念,并根据其结构特征,给出了近完全图的邻点可区别正常边色数.该结果揭示了完全图中删去一个匹配后其邻点可区别正常边色数的变化情况.

K_3∨K_n的Smarandachely邻点可区别正常边染色

图的染色问题是图论研究的主要内容之一,起源于著名的"四色猜想"问题.图G的一个正常边染色f称为是Smarandachely邻点可区别的,如果对G中任何相邻的两个顶点u与v,与u关联的边的颜色的集合和与v关联的边的颜色构成的集合互不包含.对一个图G进行Smarandachely邻点可区别正常边染色所用的最少颜色数称为G的Smarandachely邻点可区别正常边色数,简称为G的SA-边色数,记为χ′sa(G).讨论K3∨Kn的SA-边色数,得到相应的结果.

K_m∨K_n的Smarandachely邻点可区别正常边染色

研究图K-m∨Kn的Smarandachely邻点可区别正常边染色,讨论K-m∨Kn的SA边色数,得到正整数n≥4且n为偶数时χ′sa(K-n-2∨Kn)=2n-1和χ′sa(K-n-1∨Kn)=2n-1;正整数n≥3且n为奇数,则χ′sa(K-n-1∨Kn)=2n;对正整数n≥2,有χ′sa(K-2∨Kn)=n+3.

C_m·F_n的邻点可区别边色数

Fn表示阶为n+1的扇,当m个Fn的扇心连成圈时,用Cm·Fn表示.设Cm=u1u2…unv1,V(Cm·Fn)={ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Cm·Fn)=E(Cm)∪{uivij|i=1,2,…,m;j=1,2,…,n}∪{vijvi(j+1)|i=1,2,…,m;j=1,2,…,n-1}.研究Cm·Fn的邻点可区别的边色数.

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

通过将图G和H的合成图G[H]分解成一个直积图G□H和一个二分图Z的边不交并的方法,得到了χs'(G[H])≤χs'(G□H)+χ'(Z),χs'(P3[Pn])=2n+2,n=2,3;2n+3,4≤n≤10{,其中χs'(G)表示G的点可区别正常边色数.

C_m∨K_n的邻点可区别的边色数(英文)

得到了联图Gm∨Kn的邻点可区别的边色数.

图的邻点可区别正常边染色

图的邻点可区别正常边染色是指图G的一个正常边染色f使得任意相邻两点的着色集合不同.针对染色色数的上界进行研究,通过Vizing定理以及Lovasz一般局部引理,用概率方法得到了邻点可区别正常边染色色数的一个较好的上界Δ+4.

单圈图的邻点全和可区别全染色

用结构分析法完整刻画单圈图U的邻点全和可区别全染色,并得到当U■C_(n)且n■0(mod 3)时,ftndiΣ(U)=Δ(U)+2;其他情况下,ftndiΣ(U)=Δ(U)+1.表明邻点全和可区别全染色猜想在任意单圈图上都成立.

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.

P_n^2的Mycielski图的邻强边色数和邻点可区别全色数

定义新图Pn2,并在n≥3时,确定Pn2的Mycielski图的邻强边色数和邻点可区别全色数,构造一个M(Pn2)的邻点可区别全染色法.

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

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

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

几类乘积图的邻点可区别的边色数

设G是阶数不小于3的简单连通图,G的k-正常边染色称为是邻点可区别的,如果对G任意相邻两顶点关联边的颜色集合不同,则k中最小者称为是G的邻点可区别的边色数.本文给出了几类乘积图的邻点可区别的边色数的上界,并由此得到一些乘积图的邻点可区别的边色数.

P_n^k的邻点可区别正常边染色

主要讨论了Pkn的邻点可区别正常边染色,具体验证了邻点可区别正常边染色色数的猜想对该类图是成立的.

两类完全4-部图的邻点可区别正常边染色

主要讨论了两类完全4-部图的邻点可区别正常边染色.具体验证了邻点可区别正常边染色色数的猜想对该类图是成立的.

完全图和星的合成的点可区别正常边染色(英文)

首先,给出了完全图K_p和星S_q的合成的点可区别正常边色数的一个上界:当p≥2,q≥4时,上界是pq+1.再利用正多边形的对称性以及组合分析的方法来构造染色,分别得到了当p=2,q≥4;p≥3,q=4;p是偶数且p≥4,q=5;pq是奇数且p≥3,q≥5时,完全图K_p和星S_q的合成的点可区别正常边色数.

几类弱积图的邻点可区别一般边染色

讨论了弱积图邻点可区别一般边染色,给出了P_(2n)×K_m,C_(2n)×C_(2m),C_(2n+1)×C_(2m+1),C_(2n+1)×K_m的邻点可区别一般边色数,得到了当G和H都无孤立边且色数均至少为3时,G×H邻点可区别一般边色数至少为3的结论.

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义My-cielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}。讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。

P_n∨P_m的邻点可区别边染色

对于图的邻点可区别染色,给出了路的联图PnPm的邻点可构别边色数.

中间图的邻点可区别全染色

设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色.这样的k中最小者称为G的邻点可区别全色数.本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.