不含相交三角形平面图无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色.图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.为研究平面图的无圈边色数的上界,利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形的平面图的无圈边色数不超过Δ（G）＋7.     

Halin图的均匀染色

Ｈａｌｉｎ图是最小广东 小于３的３－连通平面图,且存在一个面,删除关联于该面的所有边后是一棵树。称图Ｇ的均匀Ｋ－可着色的,如Ｇ的顶点集Ｖ１、Ｖ２、…Ｖｋ,使｜｜Ｖｉ｜－｜Ｖｊ｜｜≤１（０≤ｉ〈ｊ≤ｋ）;称使图Ｇ的均匀ｋ－可着色的最小整数ｋ为Ｇ的均匀色数,记为Ｘｅ（Ｇ）。本文对非Ｋ４的Ｈａｌｉｎ图图证明了当△（Ｇ）≠４时,对任意的整数Ｋ≥「△（Ｇ）／２」＋１;当△（Ｇ）＝４时,对任意整数的Ｋ≥４,Ｇ     

关于(k,d)─图的性质

（ｋ，ｄ）－图是Ａ，Ｖｉｎｃｅ在１９８８年研究图的星着色时给出的定义．（ｋ，ｄ）－图在研究图的星着色中起着非常重要的作用．本文给出了一些（ｋ，ｄ）－图的，＆质，并根据这些性质构造了一个４－正则，４－连通的平面图，其星色数为４．     

围长较大的平面图的全染色的一个结果

图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ＂（G）为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ（G）＋2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ（G）＋1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ（G）＋1.     

不含3-圈和4-圈的平面图的列表均匀染色

任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「｜V（G）/k｜」个点上出现,则称G是k-均匀可选择的．若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的．应用discharge方法讨论了不含3-圈和4-圈的平面图的结构,证明了对于不含3-圈和4-圈的平面图G,当k≥{max△（G）,6）时,G是k-均匀可选择的,同时G也是k-均匀可染的．     

图P_m与P_n的Cartesian积图的邻点可区别I-全染色方法

图G的I全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同。在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合。图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等。对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数。应用构造具体染色的方法给出Pm与Pn的邻点可区别I-全色数。     

一类Halin—图的均匀色数

对△（Ｇ）＝４的Ｈａｌｉｎ－图证明了｜Ｖ（Ｇ）｜≠０（ｍｏｄ３）时，对任意整数的ｋ≥「△（Ｇ）／２」＋１，Ｇ是可均为Ｋ－可着色的。从而证明了这类Ｈａｌｉｎ－图的均匀染色数的下界是「△（Ｇ）／２」＋１。     

Pm∨Pn点可区别全染色

设f是图G的一个使用了k种色的正常全染色．对G的任意顶点u,用Cf（u）或C（u）表示在f下点u的颜色以及与u关联的所有边的颜色构成的集合,如果对G的任二不同顶点u与v,均有C（u）≠C（v）,那么称,为G的点可区别（正常）全染色．使得G有点可区别正常全染色的最小的k叫做G的点可区别全色数,本文给出Pm∨Pn的点可区别全色数（2≤m〈n）．     

特殊积图的无圈边染色

研究简单图的笛卡尔积图的无圈边染色及最小色数（标记为＇a（G））的问题,利用图分解、构造染色等方法给出了G×H,4G×C4,T1×T2×…×Tn,Qn等笛卡尔积图的无圈边色数.     

图W_(n,2)与图F_(n,2)的邻点可区别均匀E-全染色

对简单图G,如果图G存在一个染色法f,使得任意两个相邻的顶点染不同的颜色;任意一条边与其关联的点染不同的颜色;任意两个相邻的点的色集合不相同,并且任意两色所染元素的数目之差不超过1,则称该染色法f为G的邻点可区别均匀E-全染色,其所用最少颜色数称为该图的邻点可区别均匀E-全色数。讨论了图Wn,2与图Fn,2的邻点可区别均匀E-全染色,并得到了它们的均匀E-全色数。     

一种构造k-色临界图的方法

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。     

类比法在图染色中的应用

文章主要通过类比最大度为3的平面图的边面色数的证法,证明最大度为3的1-外平面图的弱边面染色这一例子,来展示类比法证明在图染色中的应用,这种方法对图染色的进一步研究具有一定的借鉴意义。     

关于△(G)=6的2-连通外平面图的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k-正常全染色,f称为是邻点可区别的,如果对G的任意相邻的两顶点其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.本文得到了△(G)=6的2-连通外平面图的邻点可区别全色数.     

类平面图的结构性质与边面全染色

通过研究2-连通且恰有1个内点的平面图G的结构性质,得到G的边面全色数为xef(G)≤6=△(G)△△((GG))≤>55,从而证明了平面图边面全色数猜想对于这类图成立.     

路的笛卡尔乘积图的邻点可区别全染色

一个正常的全染色满足相邻顶点的顶点及其关联边所用的色集合不同时,称为邻点可区别全染色,其所用的最少的颜色数称为顶点可区别全色数。刻画了路与路的笛卡尔乘积图的邻点可区别全色数。     

具有禁止路的条件色数

图G的一种P－着色是分配颜色到它的顶点，使得同一色类的导出子图具有性质P，图G的P－色数χ（G，P）是G的具有k种颜色的P－着色的最小数k。研究了当P这一性质是禁止路Pj时的P－色数，且把这一色数记作χ（G，^┐Pj)，给出了一些特殊图类χ（G，^┐Rj）的值。     

联图Wm∨Pn的邻点可区别全染色

若一个正常全染色其相邻顶点的色集不同时,就称之为邻点可区别全染色,邻点可区别全染色所用颜色的最小数称为邻点可区别全色数.本文研究了联图Wm∨Pm（n≥4）的邻点可区别全色数。     

关于一些图的Double图的全色数

图的全染色是指对顶点和边同时染色,使得相邻或相关联的元素染不同的颜色,其所用最少染色数称为全色数,记为ΧT（G）.本文得到了星、扇和轮的Double图的全色数.     

平面图的星色数

由Ｖｉｎｃｅ引进的星色数的概念是图的色数的一个自然推广，它们之间有着许多类似的性质．本文给出了一类星色数为３．５的平面图，回答了Ｖｉｎｃｅ提出的部分问题．     

一类K4—同胚图色唯一性的新进展

证明了：若ｉ,ｊ,ｋ,Ｌ,ｍ,ｎ中有三个数相等,而另外三个数大于此数且互不相等,则Ｋ４（ｉ,ｊ,ｋ,Ｌ,ｍ,ｎ）是色唯一的。