哈林图的弱边面染色

设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是最好可能的.     

外平面图的弱完备染色

假设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-可染的。     

哈林图的弱点边染色

假设e1和e2是两条相邻边,若它们关联同一个面且在该面的边界上连续出现,则称e1和e2是面相邻的.平面图G是弱点边k-可染的是指存在映射π:V (G)∪E(G)→{1,···, k},使得任意两个相邻的顶点,任意两条面相邻的边,以及任意两个相关联的顶点和边都染不同的颜色.文中利用数学归纳法证明了:哈林图(Halin graph)是弱点边5-可染的,并给出可达到上界5的例子.     

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

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

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射Φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足Φ(x)≠Φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)十1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=Φ,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

系列平行图的边面染色

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

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

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

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

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

Plane graphs of maximum degree Δ ≥ 7 are edge-face (Δ + 1)-colorable

A plane graph G is edge-face k-colorable if its edges and faces can be colored with k colors such that any two adjacent or incident elements receive different colors. It is known that every plane graph G of maximum degree Δ ≥ 8 is edge-face (Δ + 1)-colorable. The condition Δ ≥ 8 is improved to Δ ≥ 7 in this paper.     

Plane Graphs with Maximum Degree 6 are Edge-face 8-colorable

A plane graph G is edge-face k-colorable if the elements of \({E(G) \cup F(G)}\) can be colored with k colors so that any two adjacent or incident elements receive different colors. Sanders and Zhao conjectured that every plane graph with maximum degree Δ is edge-face (Δ +  2)-colorable and left the cases \({\Delta \in \{4, 5, 6\}}\) unsolved. In this paper, we settle the case Δ =  6. More precisely, we prove that every plane graph with maximum degree 6 is edge-face 8-colorable.     

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G).     

Facial unique-maximum colorings of plane graphs with restriction on big vertices

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and Göring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This improves a previous result for subcubic plane graphs by Andova et al. (2018). We conclude the paper by proposing some problems.     

不含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)-可染的.     

On 3-choosability of triangle-free plane graphs

It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

Note on 3-choosability of planar graphs with maximum degree 4

Deciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are such, most of the effort was focused to solving Havel’s and Steinberg’s conjectures. In this paper, we prove that every planar graph obtained as a subgraph of the medial graph of any bipartite plane graph is 3-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.