最大度为7 且不含带弦5- 圈的平面图是8- 全可染的

若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边) 染不同的色, 则称这个图是k- 全可染的. 显然, 给最大度为Δ的图进行全染色, 至少要用Δ + 1 种不同的色.本文证明最大度为7 且不含带弦5- 圈的平面图是8- 全可染的. 这一结果进一步拓广了(Δ+1)- 全可染图类.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

不含4-圈平面图的2-距离染色

图G的2-距离染色是指映射φ:V(G)→{1,2,…,k},使得距离不超过2的顶点染不同的颜色,即若0d_G(u,v)≤2,则φ(u)≠φ(v).图G的2-距离色数是使G有一个k-2-距离染色的最小正整数k,记为χ_2(G).本文证明了不含4-圈且△(G)≥10的平面图G是(△(G)+10)-2-距离可染的.     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

不含短圈的平面图的2- 距离染色

图的2- 距离染色是将图中距离不超过2 的点对染不同的色. 本文证明了g(G) > 5 且Δ(G) > 18的平面图G 有(Δ + 6)-2- 距离染色.     

不含3,4,8-圈的平面图的2-距离染色（英文）

图G的k-2-距离染色是指映射c:V(G)→{1,2,…,k},使得对G中满足0d_G(u,v)≤2的点对u,v,有c(u)≠c(v).称χ_2(G)=min{k|G有一个k-2-距离染色}为G的2-距离色数.本文证明了不含3,4,8-圈,且△≥14的平面图是(△+5)-2-距离可染的.     

不含4-圈与7-圈的平面图是(2,0,0)-可染的

设d1,d2,...,dk是k个非负整数.若图G=(V,E)的顶点集V可剖分成k个子集V1,V2,...,Vk使得对i=1,2,...,k,由Vi所导出的子图G[Vi]的最大度至多为di,则称G是(d1,d2,...,dk)-可染的.本文证明不含4-圈和7-圈的平面图是(2,0,0)-可染的.     

不含5-圈和6-圈的平面图的(2,1)-全标号

图G的(2,1)-全标号是对图G的顶点和边的一个标号分配,使得:(1)任意两个相邻顶点标号不同;(2)任意两条相邻边标号不同;(3)任意顶点与其相关联的边标号至少相差2.两个标号的最大差值称为跨度,图G的所有(2,1)-全标号的最小跨度称为(2,1)-全标号数,记为λ_2~T(G).本文证明了如果G是一个?=p+5的平面图,且G不包含5-圈和6-圈,那么λ_2~T(G)=2?-p,p=1,2,3.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

不含4-圈和5-圈的平面图的非正常2-染色的一个新结果

设d_1,d_2,···,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V_1,V_2,···,V_k,使得对任意的i=1,···,k,V_i的点导出子图G[Vi]的最大度至多为di,则称图G是(d_1,d_2,···,d_k)-可染的,本文证明了既不含4-圈又不含5-圈的平面图是(9,9)-可染的.     

不含4,6,8-圈的平面图是3-可染的

证明了每个不含4,6,8-圈的平面图是3-可染的.     

不含短圈的平面图的存活率

设G是一个n-阶连通图(n≥2).假设火在G的某点v处燃起,消防员选择一个未着火的顶点进行保护,然后火蔓延到v的未被保护且没有着火的邻点.当火在点v处燃起时,消防员最多能保护到的顶点数记为sn(v).定义■为G的存活率.容易看到0 <ρ(G)<1.本文证明了:若平面图G不含长度从4到11的圈,则ρ(G)>1/481.     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

没有4-圈的平面图的BB-染色

设H为G的一个生成子图,(G,H)的一个BB-k染色是指一个映射f:V(G)→{1,2…,k},满足以下两条:(i)|f(u)-f(u)|≥1,uu∈E(G)\E(H).(ii)|f(u)-f(u)|≥2,uv∈E(H).定义(G,H)的BB-色数xb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文证明了...     

不含4圈的平面图的全色数

用Δ(G), χ_ve(G)分别表示图G的顶点最大度和全色数.Vizing猜想: 对任何 简单图G, Δ(G) +1≤χ_ve(G)≤Δ(G)+2. 即使对于平面图, 这一猜想仍未获得完整的证明, 唯一待完成的困难情形是Δ(G)=6. 本文证明:若Δ(G)=6的平面图G不含有4圈, 则χ_ve(G)≤8.这一结果和以前在该问题上的已知结果表明：对于不含有4圈的平面图，Vizing猜想是正确的.     

不含4-圈和9-圈的平面图是(2,0,0)-可染的

设d_1,d_2,...d_k为尼个非负整数.若图G的顶点集V可划分成k个子集合V_1,V_2…,V_k,使得对于任意的i∈{1,2,...,k},由V_i导出的子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,...,d_k)-可染的.1976年,Steinberg猜想:不含4-圈和5-圈的平面图是(0,0,0)-可染的.在Steinberg猜想的驱动下,人们证明了以下三个结论:(1)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是列表(1,1,1)-可染的;(2)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是(1,1,0)-可染的;(3)对每一个i∈{5,6,7,8},不含4-圈和i-圈的平面图是(2,0,0)-可染的.为使结论(3)更加完整,本文证明不含4-圈和9-圈的平面图是(2,0,0)-可染的.     

最大度为8不含特定子图的平面图的全染色

全染色是对图G的顶点和边同时进行正常染色,至少要用Δ+1个色才能对图G进行正常全染色.本文运用权转移的方法,证明了最大度为8的不含特定子图的简单平面图是9-全可染的.     

外平面图的全染色与列表全染色

本文证明了,如果G是满足条件Δ(G)≥4的外平面图,则x_T~L(G)=Δ(G) 1,同时对Δ(G)=3给出了XT(G)=Δ(G) 1的简短的新证明,从而蕴含Δ(G)≥3时,XT(G)=Δ(G) 1,其中XT(G)是G的点边全色数,x_T~L(G)是G的点边列表全色数。     

若干圈限制平面图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’_st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’_st(G)≤[1.5Δ」+10;(3)若g=7,则χ’_st(G)≤[1.5Δ」+6.     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.