一类仙人掌图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’ _st(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图C_n·C_m(n≥3,m≥3)的星边色数,从而推广已知结果 .     

不含4-,5-圈且无相交3-面的平面图的星边染色

图 G 的星边染色是指 G 的一个正常边染色满足 G 中无长为4的路（或圈）是2-边染色的.使得图 G 有星边染色的最小颜色数 k 称为 G 的星边色数,记为 χ^′_st (G ) .证明了若平面图 G 不含4-5-圈且无相交3-面,则χ^′_st (G )≤ [1.5]Δ + 10     

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

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

最大度为3的2-连通外平面图的星边染色

如果图G中没有长为4的路是2-边染色的,那么称图G的一个正常边染色是星边染色的.使得G有星边染色的最小颜色数称为G的星边色数,记作X1s(G).研究了最大度为3的2-连通外平面图的星边染色,证明了4≤X1s(G)≤6,确定了一些特殊外平面图的星边色数.     

平行四边形六角系统的星边色数

如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此边染色是G的一个星边染色.对G进行星边染色的最小颜色数称为G的星边色数.文章研究了平行四边形六角系统的星边染色,并证明了平行四边形六角系统的星边色数等于4.     

几类r-冠图的星边染色

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数.     

平面图无圈边着色的一个结果

图G的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。     

最大度不小于7的图的星边色数的一个上界

定义了星边染色和星边色数X's(C),证明了若图G的最大度△≥7,则X's(G)≤[16(△-1)3/2].此结果包含了若图G是最大度△≥12的线图,则Xs(G)≤[16(△-1)3/2].     

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

Halin图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立，且当Δ≤4时，其色数不超过5；当Δ≥5时，其色数等于最大度。