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

图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.     

外部平面图的平方图的染色

图G的平方图，记作G^2，是一个以原图的顶点集为顶点集，若原图中两点的距离不大于2则连以边所成的图．本文确定了圈的平方图的色数．对于外部平面图，得到以下结论：设G是一个最大度为△(G)的简单连通外部平面图，G≠C5．则x(G^2)≤△(G) 2．     

无平方因子数的上界估计

设k、m、n∈N,对于给定的正整数n∈N,若存在屯使得对任意m∈N,都有m^k n,则称n为无k次幂因子数．特别地,若k=2。则称n为无平方因子数．利用初等方法,研究无平方因子的性质,进一步的获得了第n个无平方因子数的一个上界估计,并给出了参考文献中的一个评注．     

最大度为4的平面图的平方染色

证明了若G为最大度Δ(G)≤4且不含4,5,6-圈的平面图,则χ(G2)≤Δ(G)+7.     

图的全本征数的一个新上界

Cockayne,Dawes和Hedetniemi 证明了对于至少有三个点的连通图G,G的阶数P和G的全本征数γ_t(G)满足关系式γ_t(G)≤2p/3p。本文进一步研究了图G的全本征数。对于一个全本征数不低于3的连通图G,若G的最小度δ(G)不低于3且不超过P-4,则G的全本征数γ_t(G)不超过数x的整数部分,其中,x=2P/3-2δ(G)/3 4/3     

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

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

不含相交三角形的平面图的无圈边色数的新上界

图G的无圈边染色是图论染色的重要研究对象,为得到平面图的无圈边色数的上界,利用差值转移方法和平面图的结构性质,证得了不含相交三角形的平面图的无圈边色数不超过Δ(G)+6。     

平面图线性2-荫度的一个上界

设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2（G）。得到了平面图线性2-荫度的上界：若Δ≡0,3（mod 4）,则la2（G）≤「Δ/2棢＋8;若Δ≡1,2（mod 4）,则la2（G）≤「Δ/2棢＋7。     

Reexploring the upper bound for the chromatic number of graphs

The upper bound of the chromatic number of simple graphs is explored. Its original idea comes from Coffman, Hakimi and Schmeichel, who recently studied the chromatic number of graphs with strong conditions. In this paper, corresponding conditions are weakened and the result proves that of Ershov and Kozhukhin's.     

图的星边星-全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.     

图的点可区别星边色数的一个上界

图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.     

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

图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的最大度.     

图的邻点可区别星边色数的一个上界

提出了图的邻点可区别星边染色及邻点可区别星边色数χ’ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ’ass(G)≤「32Δ32?。     

临界图独立数的上界

1968年,Vizing猜想,对于n阶的△临界图G,其独立数a（G）≤n/2．利用著名的Vizing邻接引理和Fiorini不等式的证明方法,证明了如果临界图G的一个最大独立集中主顶点个数不超过1,则猜想成立,从而改进了Luo等的一个结果．     

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

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

平面图平方的最小度

设G是一个没有4-圈的平面图,G的平方图G2定义在V(G)上,使得2个点u和v在G2中是相邻的当且仅当它们在G中的距离为1或2.证明了:δ(G2)≤Δ(G) 33,并且当δ(G)≥4时有δ(G2)≤16.其中,δ(H)和Δ(H)分别表示图H的最小度和最大度.     

图的集合边色数

给出了集合边色数的定义。运用结构图论的方法,给出了集合边色数的下界以及图与其顶点删除子图、边删除子图的集合边色数的关系。