围长不小于6且最大度至少为8的平面图的无圈列表边染色

对图G的一个正常边染色,如果图G的任何一个圈至少染三种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G)都有ф(e)∈L(e),则称ф为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.证明若图G是一个平面图,且它的最大度△≥8,围长g(G)≥6,则a′_(list)(G)=△.     

1-平面图的结构性质及其在无圈边染色上的应用

一个图称为是1-平面的如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文描述了任意1-平面图中小于等于7度点之邻域的局部结构,解决了由Fabrici和Madaras提出的两个关于1-平面图图类中轻图存在性的问题,证明了每个最大度是△的1-平面图G是无圈列表max{2△-2,△+83}-边可选的.     

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

不含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.     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

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

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

图的围长与无圈边色数之间的关系

对于一个图G的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在[1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．     

没有短圈的平面图的边选择性

证明了Δ=5且没有4-圈或6-圈的平面图是6-边可选择的. 由此结果和其他已知结果推出: 给定一个整数 k∈{3,4,5,6}, 没有k-圈的平面图G是(Δ+1)-边可选择的, 其中D表示图G的最大度.     

最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

稀疏图与系列平行图的列表动态染色

图的(列表)动态染色模型可用于解决信道分配中的一些关键问题,是图论和理论计算机科学领域的一个重要的研究方向.Kim和Park (2011)给出了任何最大平均度小于8/3的图的列表动态色数至多为4的证明.然而,由于具有5个顶点的圈C₅的最大平均度为2且列表动态色数为5,因此Kim和Park的上述结论是错误的.基于此,本文证明了任何最大平均度小于8/3的普通图(每个连通分支都不与C₅同构的图)的列表动态色数至多为4,且该上界4是最优的,从而对Kim和Park的结果进行了修正.与此同时,本文证明了如果图G是系列平行图,则当其是普通图时,其列表动态色数至多为4,且该上界4是最优的,当其不是普通图时,其列表动态色数恰好为5,从而将Song等人(2014)的结果“任何系列平行图的列表动态色数至多为6”进行了改进.     

平面图的单射边染色

图G的k-单射边染色是指映射f:E(G)→{1,2,…,k},若e₁,e₂和e₃是G中的连续边,则f (e₁)≠f(e₃).称χ’_i(G)=min{k|G存在k-单射边染色}为图的单射边染色数.本文证明了:对g(G)≥6的平面图G,有χ’_i(G)≤3Δ(G)-2,对g(G)≥26且Δ(G)≤3的平面图G,有χ’_i(G)≤4,对g(G)≥16且Δ(G)≥4的平面图G,有χ’_i(G)≤Δ(G)+1,其中g(G)表示平面图G的围长.     

k-方图的邻点可区别无圈边染色

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_^(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数.     

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

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

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

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

没有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-圈又不含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)-可染的.     

图的邻点可区别无圈边染色的一个界

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.应用概率的方法得到了图G的一个邻点可区别无圈边色数的上界,其中图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)-可染的.