稀疏图的r-动态染色

通过分析极小反例的结构性质,运用权转移的方法,研究了对于mad(G)<14/5的稀疏图G的r-动态染色数,证明了对于满足mad(G)<14/5的图G,若r≥9,则χr(G)≤r+2.研究结果推广了稀疏图r-动态染色的已知结果.

围长至少为6平面图的injective-染色

为了进一步探究平面图的injective-染色,通过分析临界图的结构性质并利用权转移方法,证明了围长至少为6,Δ(G)≥9且6-圈与6-圈不交的平面图G,有χ_(i)(G)≤Δ(G)+1.所得结果推广了平面图injective-染色的已知结果.

最大度为5的简单图的2-距离列表染色

通过对极小反例G的结构分析,利用权转移的方法,证明了:对于Δ(G)≤5的图G,若mad(G)<20/7,则χl2(G)≤10;若mad(G)<19/6,则χl2(G)≤11.这一结果改进了现有的部分结论.

围长至少是6的平面图的injective-边染色

为了进一步探究平面图的性质,运用极小反例和权转移的方法,研究了围长至少为6且6-圈与7^--圈不相交的平面图G的injective-边染色数,并证明该染色数的上界至多为3Δ(G)-3.研究成果改进了现有injective-边染色数的一个结论.

平面图的强边染色

图G的强边染色是在正常边染色的基础上,要求距离不超过2的任意两条边染不同的颜色,强边染色所用颜色的最小整数称为图G的强边色数。本文首先给出极小反例的构型,然后通过权转移法,证明了g(G)≥5,Δ(G)≥6且5-圈不相交的平面图的强边色数至多是4Δ(G)-1。

5^——圈和5^——圈不交的平面图的injective-列表染色

通过构造一个(Δ+6)-临界图,运用权转移的方法证明了:对于5^--圈和5^--圈不交且Δ(G)≥18的平面图G,有χi^l(G)≤Δ(G)+6.所得结果研究了平面图G在短圈不交的限制条件下的injective-列表染色的问题.

平面图的动态染色

通过讨论极小反例图的结构性质,运用权转移方法,研究了r≥11,围长至少为5且5-圈与5-圈不相邻的平面图G的动态色数,证明了这类平面图G的r-动态色数的上界至多为r+4.研究成果改进了现有动态色数的一个结论.

围长至少为5的平面图的injective-染色

为了进一步探究平面图的injective-染色,利用临界图的结构性质和权转移方法,研究了围长至少为5,最大度至少为40的平面图的injective-染色数,并证明了该染色数的上界至多为Δ+2.所得结果推广了平面图injective-染色的已知结果.

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.

最大度为4的平面图的2-距离染色

2-距离染色是使得距离至多为2的顶点染不同色的一种顶点染色.1977年,Wegner猜想9种颜色可以使最大度为4的平面图有一个2-距离染色.本文证明了最大度为4的平面图用13种颜色可以使之有一个2-距离染色,而对不含三角形且最大度为4的平面图用11种颜色就可以了.

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_(α)(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_(α)(G)≤Δ(G)+1.

围长至少为5的平面图的injective-染色

图G的injective k-染色是指映射c:V(G)→{1,2,…,k},使有公共邻点的两个顶点u,v满足c(u)≠c(v),用X_i(G)表示使G有一个injective k-染色的最小正整数k.对g(G)≥5的平面图G,若△(G)≥20,证明了X_i(G)≤△+3.

稀疏平面图的2-距离染色（英文）

图G的k-2-距离染色是指一个映射φ:V(G)→{1,2,…,k},满足对任意距离小于等于2的顶点对u,v,有φ(u)≠φ(v).2-距离色数χ_2(G)是指使得图G是k-2-距离染色的最小的k.本文证明:对于g(G)≥5且△(G)≥44的平面图G,有χ_2(G)≤△(G)+4.

平面图的单射边染色

图G的k-单射边染色是指映射f:E(G)→{1,2,…,k},若e1,e2和e3是G中的连续边,则f(e1)≠f(e3).称χ’i(G)=min{k|G存在k-单射边染色}为图的单射边染色数.本文证明了:对g(G)≥6的平面图G,有χ’i(G)≤3Δ(G)-2,对g(G)≥26且Δ(G)≤3的平面图G,有χ’i(G)≤4,对g(G)≥16且Δ(G)≥4的平面图G,有χ’i(G)≤Δ(G)+1,其中g(G)表示平面图G的围长.