极大外平面图的星边染色

如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作x′s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图Gn,有6≤x′s(Gn)≤n-1成立,并且上界和下界都是可达的.     

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

本文证明了,如果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=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

极大外平面图在边界条件下的4染色

本文利用极大外平面图的对象变换研究它的染色，并给出了特征向量的概念，证明了任意两上有公共界环的极大外平面图都可以通过一系列对角变换互相得到，进而证明了有公共标定界环的两个极大外平面图在某些条件下有公共４染色。     

外平面图的弱边面染色

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

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的星边染色是指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.     

△(G)=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当且仅当存在相邻的最大度点.     

极大外平面图（r,k）——扇的4染色

定义了一类极大外平面图：(r,k）--扇。证明了当G是以r个顶点的圈Qr为标定界环的(r,k）一扇,G'是以Qr为标定界环的任意极大外平面图时,G和G'有公共四染色;同时对△(G)=r-3的极大外平在图也得到相同的结论。从而证明了四色定理的等价命题在给定条件下成立。     

极大外平面图的边面全色数

本文给出了△（Ｇ）≤６的极大外平面图的边面全色数，其中△（Ｇ）表示Ｇ的最大度。     

A SEVEN-COLOR THEOREM ON EDGE-FACE COLORING OF PLANE GRAPHS

1 IntroductionLet G be a plane graph with the vertex set V(G), the edge set E(G), the faCe set F(G),and the maximum degree A(G). The edge-face chromatic number X.I (G) of G is the ndnimumnunther of colors assigned to E(G) U F(G) such that aliy two adjacent or incident elements havedifferent colors. By the definition, X.,(G) 2 A(G) is trivial. In 1975, MelnikovI4J raised thefollowing conjecture.,Coniecture 1.1 For every plane graph G, X.J (G) 5 A(G) 3.The conjecture has been ton…     

若干图的强染色

图 G(V,E)的一正常 k-染色 σ称为 G(V,E)的 - k-强染色当且仅当对任何两个不同顶点 u和 v,只要d(u,v)≤ 2 ,则 u、v染不同颜色 (这里 d(u,v)表示 u,v之间的距离 ) ,并称 xs(G) =min{ k|存在 G的 - k-强染色 }为 G的强色数 ,本文得到 θ-图 ,Cm,n图 ,Halin图的强色数 xs(G)     

由均匀染色导出的强Chernoff界

本文研究了相关变量的Chernoff问题. 利用相关变量构造图的方法, 利用均匀染色的结果, 获得了更强的Chernoff界, 推广了Chernoff不等式在相关随机变量的不等式下的界.     

图的关联色数和关联着色猜想

本文综述了图的关联着色的已有结果，证明了关联着色猜想对于完全3—部图和高度留成立，确定了路、圈、扇、轮和加边轮等特殊图类的关联色数．     

一些积图的点可区别均匀边色数

本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC).     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.     

Mycielski图的循环色数

通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.     

一类星色数为4的平面图

图的星色数的概念是Vince在1988年提出的,它是图的色数的一个推广.本文构造了一类星色数是4的平面图.     

最大度不大于5的Halin-图的点强全染色

图G(V,E)的一正常k-全染色f称为G(V,E)的一k-点强全染色当且仅当任意( A)v∈V(G),N[v]中的元素染不同色,其中N[v]={u|uv∈V(G)}U{v},并且XusT(G)=min{k|存在G的k-点强全染色}称为G(V,E)的点强全色数.本文得到了△(G)≤5的Halin-图G(V.E)的XusT(G),并提出如下猜想设G(V,E)为每一连通分支的阶数不小于6的图,则XusT(G)≤△(G)+2,其中△(G)表示图G的最大度.