点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

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

设G是简单图，f是从V（G）UE（G）到{1,2，…，k）的一个映射．对每个u∈y（G），令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果，是k-正常全染色，且对任意u，v∈V（G）（u≠v），有c（u）≠c（v），那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法，证明了对任意最大度A≥2的图G，χvt（G）≤32（△＋1）．     

图的D(2)-点可区别边色数的一个上界

用图的概率方法中的赋权局部引理得到最大度不小于5的图的D(2)-点可区别边色数的一个上界是4(2d4-d3-4d2 5d-1)/d-1,这里d是图G的最大度.     

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）的点可区别边色数.     

Wm与Pn(n≤3)联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E(G)到{1,2,…,k}的映射,且满足V 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),研究了WmVPn(n≤3)的点可区别边染色,给出了WmVPn(n≤3)的点可区别边色数.     

正则图点可区别全色数的一个上界

图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的色.应用概率的方法得到了n个点的k-正则图G的一个点可区别全色数的较小上界.     

图Pm∨Wn的点可区别边色数

对网G的正常边染色，若满足不同点的点所关联边色集合不同，则称此染色法为点可区别的边染色法，其所用最少染色数称为该罔的点可区别边色数．得到了路与轮的联网的点可区别边色数。     

PmVPn的点可区别边色数

研究了Pm V Pn的点可区别边染色,并得到了PmVPn的点可区别边色数.     

两类图的点可区别边染色数

证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图.     

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

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

一类图的邻强边色数的上界

证明了当图G的最大度Δ(G)恰以n的某个函数为界时,G的邻强边色数χ′as(G)≤│cn│,其中0相似文献   

图的无圈全色数的一个上界

图G一个正常全染色f被称为无圈全染色,若G中无2-色圈.图G的无圈全色数,标记为χaet'(G),是图G的无圈全染色中所用的最少颜色数.在这篇论文中,证明了若G是一个Δ≥3的图,那么χaet'(G)≤32Δ,这里Δ是G的最大度.     

高度正则图的强边色数

设f是图G的一个正常边着色，若对G中任意不同的两点u,v，着在与u关联的边上的色集和着在与v关联的边上的色集不同，则称f为强边着色。满足此条件的最小色数称为G的强边色数，记为X^-′（G）。本文确定了对n阶（n-2）-度正则图G，X^-′（G）=n，当n≥6时，对其补图为Hamilton圈的n阶（n-3)-正则图G，X^-′（G）=n-1，还给出了对任意的一条边e，X^-′（G-e)≤X^-′（G） 1的一个充分条件和X^-′（G-e）=X^-′（G） 2的必要条件。     

K_n-｛v_1v_2,v_3v_4,v_5v_6,v_7v_8｝(n≥20,n≡0(mod2))的点可区别边色数

研究n阶完全图Kn(n≥20,n≡0(mod2))去掉4条独立边后的点可区别边染色,并给出了图Kn-{v1v2,v3v4,v5v6,v7v8}(n≥20,n≡0(mod2))的点可区别边色数。     

幂图的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

若干直积图的邻点可区别VE-全色数

应用穷染递推的方法研究了路与路(圈、星、扇、轮、完全图)构成的直积图的邻点可区别VE-全染色,并给出了具体的染色方案,进一步得到了邻点可区别的VE-全色数.     

稀疏图平方图的染色数上界

图G的平方G2定义为顶点集V(G)=V(G²), 并且uv∈E(G²)当且仅当u和v之间的距离至多为2. G²的色数χ(G²)是指使得G²存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G²)≤3Δ(G)+1; 如果mad(G)≤4且Δ(G)≥8, 则χ(G²)≤3Δ(G)+5.