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

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

系列—平行图的列表染色

系列－平行图是没有子力与Ｋ４同胚的图。设Ｇ为一个系列－平行图。如果对任意的边ｅ∈Ｅ（Ｇ）,有ｆ（ｅ）≥ｍａｘ（４,Δ（Ｇ））,则Ｇ是ｆ－可列表染色的同时还确定了所有系列－平行图的边色数。     

一类图的列表强边染色

给出了列表强边染色的定义,证明了若G为d(x)+d(y)≤5,则强边选择数Sχ′l(G)≤6.     

无相交三角形平面图的邻点可区别边染色

图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'_a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'_a(G)≤max{Δ(G)+2,10}。     

关于平面图的边面全着色

定义了平面图的边面全色数，提出了相应的猜想，证明了无割点外平面图的最大度不少于７时，其边面全色数等于其最大度。     

平面图的无圈边染色

一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.     

Δ(G)=3的图的列表强边染色

证明了若G为Δ(G)=3的图,则强边选择数Sχ′l(G)≤11.     

Halin图的边列表染色

图的染色是图论的重要研究内容之一．平面图染色是其中的一个主要方面．有各种各样的染色方式,近来,又出现了列表染色［１］．定义１称图Ｇ是ｋ－边可选择的．如果任给ｅ∈Ｅ（Ｇ）,和边ｅ的任给颜色集Ｌ（ｅ）,｜Ｌ（ｅ）｜＝ｔ,都可以选一种颜色σ（ｅ）∈Ｌ（ｅ）...     

△（G）=3的图的列表强边染色

证明了若G为△（G）=3的图,则强边选择数SХl＇（G）≤11．     

2—树的点边列表染色

给出了点边列表染色的定义,证明了对2－树,当△（G）＞3时,点边选择数为图的最大度加1。     

关于着色参数Nordhaus－Gaddum问题的若干注记

分别以Ｘ（Ｇ）、Ｘ１（Ｇ）、Ｘ２（Ｇ）记图Ｇ之色数、边色数和金色数，对任意Ｐ阶图Ｇ及其补图，当Ｘ１（Ｇ）、Ｘ１（Ｇ）不为零时，本文得到下面三个Ｎｏｒｄｈａｕｓ－Ｇａｄｄｕｍ型乘积的下界：对于每一工整数Ｐ，这三个下界均可达到。     

三角金字塔网的点、边、全色数

确定了三角金字塔网TPL的点色数X（TPL）=4,当L≥4时,它的边色数为x＇（TPL）=12,它的全色数为疋;（TPL）=13．所得结果进一步完善了三角金字塔网TPL的知识体系．     

不含3-圈的1-平面图的边染色

利用权转移方法证明了最大度Δ≥7且不含3-圈的1-平面图是Δ-边可染的。     

最大度顶点互不相邻的高度图的全色数

研究了最大度顶点互不相邻的高度图的全色数．得到：设图Ｇ的最大度顶点是互不相邻的，且δ（Ｇ）≥３４｜Ｖ（Ｇ）｜，则ｘＴ（Ｇ）＝Δ（Ｇ）＋１     

图的各种一般全染色

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

图的无圈全色数的一个上界

图G一个正常全染色f被称为无圈全染色,若G中无2-色圈.图G的无圈全色数,标记为χaet'(G),是图G的无圈全染色中所用的最少颜色数.在这篇论文中,证明了若G是一个Δ≥3的图,那么χaet'(G)≤32Δ,这里Δ是G的最大度.     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

图P_n~k的着色

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论.