1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

Δ(G)≤4的外平面图的邻强边色数

研究了Δ(G)≤4的外平面图的邻强边染色,证明了Δ(G)≤χ′as(G)≤Δ(G)+1,且χ′as(G)=Δ(G)+1当且仅当存在两个最大度点相邻,其中Δ(G)和χ′as(G)分别表示图G的最大度和邻强边色数,并且提出了如下猜想:如果G是一个|V(G)|≥3(G≠C5)的2-连通图,则Δ(G)≤χ′as(G)≤Δ(G)+2.     

第一类图的一个充分条件

图G的一个k-边染色是一个映射ψ:E(G)→{1,2…k},使得每一对相邻边x和y,有ψ(x)≠ψ(y,).G的边色数χ'(G)是使得G有一个k-边染色的最小的整数k.本文证明了:如果G是一个最大度为6能嵌入到欧拉示性数非负的曲面的图,且满足下列条件之一,那么χ'(G)=6:(1)不含带弦4-圈;(2)同时不含带弦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.     

图论与中学数学竞赛(二)

六平面图平面图一个图G,如果能够把它画在平面上,且除端点外任意两条边均不相交则称G可以嵌入平面,如果图G可以嵌入平面,则称G为可平面图可平面图在平面上的一个嵌入称为一个平面图,如图17—a所示的图G是一个可平面图。图17-b所示的图G是G的一个平面嵌入即平面图。     

围长至少为5的IC-可平面图的邻点可区别边染色

给图G一个正常k-边染色φ,对G的任意两个相邻的顶点u和v,若满足与u关联的边所染颜色集合和与v关联的边所染颜色的集合不同,则称φ为图G的k-邻点可区别边染色.用χ’_a(G)表示图G的邻点可区别边色数,即使得G有一个k-邻点可区别边染色的最小正整数k.通过运用权转移方法研究围长至少为5的正常IC-可平面图的邻点可区别边染色,得到了χ’_a(G)≤max{Δ(G)+2,11}.     

外平面图的弱边面染色

假设G是一个平面图.如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻.图G的一个弱边面κ-染色是指存在映射π:E∪F→{1,…,κ},使得任意两个相邻面、两条面相邻的边以及两个相关联的边和面都染不同的颜色.若图G有一个弱边面κ-染色,则称G是弱边面κ-可染的.平面图G的弱边面色数是指G是弱边面κ-可染的正整数κ的最小值,记为χef(G).2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文证明了外平面图满足此猜想,即:外平面图是弱边面5-可染的.     

2-连通的平面图的边面染色

一个平面图G的边面色数χ_(ef)(G)是最小的颜色数,使得G中任意两条相邻的边、两个相邻的面、以及两个关联的边和面都染不同的颜色.本文证明了,若G是?≥16的2-连通平面图,则χ_(ef)(G)=?.这改进了已知结果:若G是?≥24的2-连通平面图,则χ_(ef)(G)=?.     

极大外平面图的邻强边色数

本文证明了对极大外平面图 G,Δ(G) χ′as(G)≤ Δ(G) +1,且 χ′as(G) =Δ(G) +1,当且仅当存在两个最大度点相邻 .其中Δ (G)、χ′as(G)分别表示图 G的最大度和邻强边色数 .     

不含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(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.     

平面图的单射边染色

图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的围长.     

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

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

哈林图的弱边面染色

设G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.对于任意的两条相邻边e_1和e2,如果它们关联同一个面且在该面的边界上连续出现,那么称e_1和e2是面相邻的.图G是弱边面k-可染的是指存在一个映射π:EUF→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.平面图G的弱边面染色数是指G是弱边面k-可染的数k的最小值,用_(ef)(G)表示.2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文我们给出此猜想的一个充分条件,即证明:哈林图是弱边面5-可染的,其中上界5是最好可能的.     

图的Smarandachely邻点边色数的界

对图G的一个k-正常变染色法f,若图G中任意相邻两点的相邻边色集合互相不包含,那么称f为图G的一个k-Smarandachely邻点边染色(简记为k-SEC),而最小的正整数k称为图G的Smarandachely邻点边色数.尝试应用Lovasz局部引理来得到了Smarandachely邻点边色数的上界.     

IC-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,...,G_m,使得E(G)-E(G₁)∪…∪.E(G_m),且对任意i≠j,有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

色指数临界图的一些新结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的颜色数.1965年,Vizing证明了任意最大度为△的图的边色数或者是△或者是△+1.若G是连通的,且G的每一条边e均有X′(G-e)相似文献   

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

平面图的严格邻点可区别染色

图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图H_Δ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.