最大度为6的极大外平面图的完备色数

证明了最大度为６的极大外平面图的完备色数为７。     

外平面图的弱边面染色

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

极大外平面图的星边染色

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

若干平面图的完备色数

设G是无割点平面图,X_c(G)为G的点边面完备色数,p=|V(G)|.本文证明了如G为Δ(G)≥7的外平面图,或G为p≥9且Δ(G)≥p-2,或G为Δ(G)≥14的极大平面图,则 X_c(G)=Δ(G)+1.     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．     

可平面图完备色数唯一性问题

可平面图完备色数唯一性问题赵克文（华南师范大学数学系，广州５１０６３１）我们已经知道，图的点色数、边色数，点边金色数Ｘ＿Ｔ都是唯一的。那么，可平面图的边面完备色数Ｘ唯一吗￣［２］？本文对此有结论：并非每一可平面图的完备色数都唯一，由此就产生问题：Ｘ（...     

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

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

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

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

高度平面图完备色数的一个刻划

设G是一个平面图,△(G)为G的最大度．G的完备色数x     

最大度为8不含特定子图的平面图的全染色

全染色是对图G的顶点和边同时进行正常染色,至少要用Δ+1个色才能对图G进行正常全染色.本文运用权转移的方法,证明了最大度为8的不含特定子图的简单平面图是9-全可染的.     

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.     

Game chromatic number of outerplanar graphs

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999     

On list‐coloring outerplanar graphs

We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors L (v ) for each vertex v such that (resp., ) can be L‐list‐colored (except when the graph is K₃ with identical 2‐lists). These results are best possible for each condition in the hypotheses and bounds. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 59–74, 2008     

The relaxed game chromatic number of outerplanar graphs

The (r,d)‐relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with α, and every neighbor of u that has already been colored with α is adjacent to at most d – 1 vertices that have already been colored with α. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)‐relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)‐relaxed coloring game on G. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:69–78, 2004     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

Δ(G)=5的2-连通外平面图的邻点可区别全染色

Smarandachely邻点可区别全染色是指相邻点的色集合互不包含的邻点可区别全染色,是对邻点可区别全染色条件的进一步加强。本文研究了平面图的Smarandachely邻点可区别全染色,即根据2-连通外平面图的结构特点,利用分析法、数学归纳法,刻画了最大度为5的2-连通外平面图的Smarandachely邻点可区别全色数。证明了：如果$G$是一个$Delta （G）=5$的2-连通外平面图,则$chi_{rm sat}（G）leqslant 9$。     

On adjacent-vertex-distinguishing total coloring of graphs

In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.     

Game coloring the Cartesian product of graphs

This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G^* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G^* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008