围长至少是7的1-平面图是$(1,1,1,0)$-可染的

一个图称为是1-平面图的, 如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文证明了围长大于等于7的1-平面图是$(1,1,1,0)$-可染的.     

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

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

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-平面图.现主要介绍关于以上四类图在染色方面的结果.     

围长不小于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)=△.     

最大度不小于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当且仅当存在相邻的最大度点.     

可平面图的线性2-荫度的新上限（英文）

图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+9;当△≡1,2(mod 4)时,1a_2(G)≤[△/2]+8;(2)对于不含三角形的可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+5;当△≡1,2(mod 4)时,la_2(G)≤[△/2]+6;其中△为图G的最大度.     

外平面图的弱边面染色

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

2-外平面图的无圈边色数

一个图G的无圈边染色是一个止常的边染色使得其不产生双色圈．Alon,Sudakov和Zaks（2001）猜想：每一个简单图G是无到（△（G）＋2）-边可染的,其中△（G）是G的最大度．本文对2-外平面图族证明了该猜想成立．     

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

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

无符号拉普拉斯谱半径的新上界

如果一个图存在定向满足其最大出度△~＋不超过最大度△的一半,则通过估计图的半边路径（semi-edge walk）的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界.     

List edge and list total coloring of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)- total-choosable if Δ≥16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.     

Light subgraphs in the family of 1-planar graphs with high minimum degree

A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2∨(K1∪K2) with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1∨(K1∪K2 ) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.     

系列平行图的邻强边色数

本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x'as(G)≤△(G) 1,且x'as(G)=△(G) 1当且仅当存在两个最大度点相邻,其中△(G)和x'as(G)分别表示图G的最大度和邻强边色数.     

环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.     

Equitable Coloring of Three Classes of 1-planar Graphs

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree Δ at least 15, 13 or 12 has an equitable Δ-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.     

The structure of 1-planar graphs

A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.     

A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge.In this paper,we prove that every 1-planar graph G with maximum degree Δ(G)≥12 and girth at least five is totally(Δ(G)+1)-colorable.