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）.

1-外平面图的边面全色数(英文)

一个平面图Ｇ被称为１－外平面图如果存在一个顶点ｕ 使得Ｇ－ ｕ 是一个外平面图．本文证明了Ｍｅｌｎｉｋｏｖ 的边面染色猜想对所有１－外平面图成立．

图的星边星-全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.

一些联图的邻点可区别-边全染色

讨论了C_m+C_n,S_m+S_n,F_m+F_n,W_m+W_n等一些联图的邻点可区别-边全染色,得到了它们的邻点可区别-边全色数.

关于路的k-方图的邻点可区别-边全染色和第一类弱全染色

给出了路的k-方图的邻点可区别-边全染色数和第一类弱全染色数。

关于一类三倍图的邻点可区别E-全染色

运用分析法和穷举法,研究了路,圈,星,扇,轮的三倍图的邻点可区别E-全染色,并且得到了他们的邻点可区别E-全色数。

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C’(u)≠C’(v),其中C’(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为χ’_r(G)文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题通过逐层染色的方法,得到了树的D(2)和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.

一组Nordhaus-Gaddum型定理

分别以Ｘ（Ｇ）、Ｘ１（Ｇ）、Ｘ２（Ｇ）记图Ｇ之色数、边色数和全色数，对任意ｐ阶简单图Ｇ及其补图Ｇ，本文得到以下Ｎｏｒｄｈａｕｓ-Ｇａｄｄｕｍ型结论：本文还指出，上面所有下界、上界对每个正整数ｐ均可达到。

树图的2-距离和可区别染色

根据树图的结构特点,应用数学归纳法、组合分析法及组合零点定理,研究了图G的2-距离和可区别边染色和全染色问题,得到了树的2-距离和可区别边色数和全色数。

边替换图的邻和可区别全染色

考虑图的邻和可区别全染色问题及其相关的1-2猜想.首先,利用独立消圈集法得到剖分图S(G)和三角扩展图R(G)的邻和可区别全色数;其次,当G为任意简单连通图且T为给定的特殊图时,证明边替换图G[T]满足1-2猜想.

关于C_m×C_(5n)的全色数和邻强边色数

设G是一个简单图,k为正整数,V(G)∪E(G)到{1,2,…,k}的一个映射f满足:对于任意的uv∈E(G)有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);任意的uv,vw∈E(G),u≠w,有f(uv)≠f(uw),则称f为G的k-全染色,简记为k-TC,并称ΧT(G)=min{k|G存在k-TC}为G的全色数.证明了圈Cm与圈C5n的笛卡尔积图的全色数和邻强边色数都为5.

乘积图的全色数

本文得到了有关乘积图的全色数的一些结果，并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想．特别，几乎所有的Mesh-图都是第一类图．

几类图的相邻顶点可区别的全染色

给出了几类特殊图相邻顶点可区别的全色数,如双路间和二部(V1,V2)间叠加匹配形成的系列图、双圈(prism)、双轮.并得到边连通度λ(G)=1的图相邻顶点可区别的全染色的性质.

图P_m∨W_n与W_m∨W_n的第一类弱全色数

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);则称f是G的第一类弱全染色.给出了路与轮,轮与轮联图的第一类弱全色数.

Δ(G)=3时的Halin图的边面全色数

研究３正则Ｈａｌｉｎ 图的边面全色数问题，证明了《最大度Δ（ Ｈｇ） ≥７ 及Δ（ Ｈｇ）＝ ４，５ ，６ 的Ｈａｌｉｎ 图的边面全色数》一文提出的如下猜想成立：对Δ（ Ｇ） ＝ ３ 时的Ｈａｌｉｎ 图有４ ≤χｅｆ（Ｇ） ≤５ ，这里Δ（ Ｇ） 表示图Ｇ 的最大度数，χｅｆ表示图Ｇ的边面全色数。

图的各种一般全染色(英文)

图G的正常全染色是指若干颜色给G的顶点和边的分配,使任意2个相邻顶点、2条相邻边和任一顶点与它的关联边得到的颜色不同.将正常全染色的限制条件减弱,得到了各种一般全染色,并讨论了它们的色数.

最大度△(Hg)≥7及△(Hg)=4、5、6的Halin图的边面全色数

本文证明了△(Hg)≥7及△(Hg)=4、5、6时,Halin图Hg的边面全色数。其中△(Hg)表示Halin图的最大度。

低度平面图的边面全色数

平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。

六角系统的边面点面全色数

本文得到了六角系统的边面和点面金色数．

关于若干倍图的邻点可区别边全染色

应用图的邻点可区别边全染色,给出了路、圈、星、扇和轮倍图的邻点可区别边全色数。