Δ≥9且不含相邻4-圈的平面图是(Δ+1)-全可选和Δ-边可选的

设χ'l(G),χ″l(G)和Δ(G)分别表示平面图G的列表色数,列表全色数和最大度,目前已经证明:若G是Δ≥12的平面图,则χ'l(G)=Δ,χ″l(G)=Δ+1。本文将证明:若G是Δ≥9且不含相邻4-圈的平面图,则χ″l(G)=Δ+1,χ'l(G)=Δ。     

△(G)=9且不含4-圈的平面图的全色数

用△(G)表示图G的顶点最大度.对平面图,当△(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Dischrge方法证明了最大度为9且不含4-圈的平面图的全色数等于10.     

合成图的全着色

对于任意简单图G,Δ(G)和t(G)分别表示G的最大度和全色数.本文证明了如果G的全色数满足t(G)≤Δ(G)+2,则合成图G[(?)_m]和K_n[G]的全色数满足t(G[(?)_m])≤Δ(G[(?)_m])+2,t(K_n[G])≤Δ(K_n[G])+2。     

关于Δ(G)=5的2-连通外平面图的邻点可区别全色数

给出了Δ(G)=5的2-连通外平面图的邻点可区别全色数.     

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

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

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

给出了圈的阶数至少为4的单圈图的邻点可区别全色数.如果E(G[VΔ])=,则χat(G)=Δ(G) 1,否则,χat(G)=Δ(G) 2,其中Δ(G)表示图G的最大度.     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

p_1-类图的双约束边色数

双约束边染色是指对平面图G的边进行染色,使得相邻的边染不同的颜色且在同一个面上的边也有不同的颜色.图G的双约束边色数χe/vf(G)是指对图G进行双约束边染色所需要的最少的颜色数,各种平面图的双约束边色数的上界是研究双约束边染色的焦点问题.证明了对于高度平面图中的p1-类图,恒有χe/vf(G)≤Δ(G)+1成立,其中Δ(G)为图G的最大度.     

高度平面图的L(p,q)—标号

研究高度平面图G的L(p,q)-标号问题，证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q)；h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1. 对于L(2,1)标号问题Griggs和Yeh有一著名猜想：对最大度为Δ的任意图有λ(G)Δ2. 此猜想对高度平面图是正确的.     

两类几乎外平面图的双约束边色数

阐述了几乎外平面图的概念与特点,证明两类特殊的几乎外平面图的双约束边色数恒满足max{Δ(G),FM(G)}≤χe/vf(G)≤max{Δ(G)+1,FM(G)+1},其中Δ(G)、FM(G)分别为图G的最大度和最大面度.     

不含3,4-圈的平面图的均匀染色

图的正常点染色称为均匀的,若每个色类所含的顶点数至多相差1.利用平面图的性质及换色法技巧.证明了若图G是Δ(G)≥6且不含3,4-圈的平面图,则对任意的m≥Δ(G),图G是均匀m-可染的.     

最大度为7且短圈不正常相交的平面图的全染色

一个图G的k-全染色是指用k种颜色对G的顶点和边进行染色,使得相邻或相关联的元素染不同的颜色.图G的全色数χ_T(G)是使G存在k-全染色的最小整数k.证明了最大度为7且3-圈与5-圈不正常相交的平面图的全色数是8.     

Schrijver图S_G(2k+2,k)的全色数

图G的一个k-全染色是用k种颜色对图G的顶点和边进行染色,使得任意相邻的边、相邻的顶点和相关联的顶点和边都染不同的颜色.图G的全色数是图G的k-全染色中最小的k值,记为χ″(G).Behzad和Vizing分别独立地提出了著名的全染色猜想TCC:Δ+1≤χ″(G)≤Δ+2,Δ表示图G的最大度.研究了Schrijver图SG(2k+2,k)的全色数问题,得到了χ″(SG(2k+2,k))=Δ+1=k+3,其中k≥2.     

若干图的广义字典积的全染色

设G是具有顶点集{t0,t1,…,tn-1}的轮,或扇,或星,其中t0为最大度点,且n≥5.G[hn]是图G与顶点不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积,其中每一个Hi为m阶简单图.论文得到了以下结果:(1)若H0为完全图的补图,则G[hn]的全色数为(n-1)m+1;(2)若H0为完全图,则G[hn]的全色数为mn;(3)若H0为二部图,则G[hn]的全色数为Δ(H0)+(n-1)m+1,其中Δ(H0)表示图H0的最大度;(4)若H0为m阶圈,m≥3,则G[hn]的全色数为(n-1)m+3.     

最大度是5的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.     

简单图的全染色的一个结果

简单图的全染色是图的染色理论中的一个重要问题,为了深入研究图的全色数猜想与图的最大平均度之间的关系,我们利用差值转移方法证明了最大平均度小于4的简单图的全色数满足全色数猜想;同时,还证明了最大度不小于12且最大平均度小于6的简单图G的全色数不超过Δ(G)+3.     

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.     

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

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

一类平面图的强边着色

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

含相邻三角形的平面图的列表边和列表全染色

给定一个平面图G,χ´_l(G)和χ"_l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´_l(G)≤Δ(G)+1和χ"_l(G)≤Δ(G)+2成立。