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.

关于高度极大外平面图的4染色

从最大度的角度讨论两个极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ’是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ’有公共４染色．从而证明了四色定理的等价命题在给定条件下成立．

外平面图的距离2-点可区别边色数

主要研究了外平面图的距离2-点可区别边染色的问题,给出了这类图的距离2-点可区别边色数的一个上界.采用数学归纳法,证明了:每一个最大度为Δ的外可平面图G,有χ'd2(G)≤2Δ.

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

研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a'(G)≤Δ(G)+3.

临界极大外平面图

给出了临界极大外平面图以及最大度临界极大外平面图的定义 ,并讨论了它们的性质 ,为研究极大外平面图的四染色提供了一种新方法 .

外平面图的边面列表染色

设Ｇ是无割点平面图，本文定义了Ｇ的边面列表选择数ｘｅｆｌ，证明了若Ｇ为最大度Δ（Ｇ）≥５的无割点外平面图，则Δ（Ｇ）≤ｘｅｆｌ（Ｇ）≤Δ（Ｇ）＋１。

最大度为6的极大外平面图的完备色数(英文)

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

外平面图的弱完备染色

假设G=(V,E,F)是一个平面图。如果e_(1)和e_(2)是G中两条相邻边且在关联的面的边界上连续出现,那么称e_(1)和e_(2)面相邻。图G的一个弱完备k-染色是指存在一个从VUEUF到k色集合{1,…,k}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及VUEUF中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成X_(vef)(G)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。