关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图,其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖,如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ,由此将 χ’c(G)=δ的图称为CⅠ类图,否则称为CⅡ类图. 显然,图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件,而且该条件中的下界是最好的。     

乘积图的分数染色

文中通过讨论由Hamilton圈、二部图、Ga、等图构造的Cartesian乘积图的分数染色,初步研究了Cartesian乘积图分数染色的一般规律．     

几类图的全色极大团染色

设G是一个简单图,其顶点集为V(G)而边集为E(G).图G的一个k-染色是指顶点集V(G)到色集{1,2,…,k}的一个映射.如果图G的一个点染色使G的每个极大团所有颜色均出现(这里不要求邻点染色不同),则称该染色为图G的全色极大团染色.而G的全色极大团色数是指能进行全色极大团染色的最大颜色数,记为χmaxcT(G).     

一类边覆盖临界图的构造

在图的边覆盖染色中边覆盖临界图的构造问题一直是研究的热点和难题.给出了一类边覆盖临界图的构造方法.对于任意给定的最小度δ,利用该方法可以构造出相应的一类边覆盖临界图.     

分数染色临界图及其性质

给出了分数染色临界图的定义及其一些性质。     

两类特殊图的分数色数及其临界性

本文给出了两类特殊图μm(Kn),m≥0,n≥3和GVDG′,D={0,1}的分数色数并证明它们分别是Χf(μm(Kn)),Χf(GVDG′)临界的.     

图乘积的分数色数

在文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H,我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H),这里ω(G)表示图G的最大团所含顶点的个数,χf(G)和χ(G)分别表示图G的分数色数和色数.从而我们可以通过图G和H本身的性质来对它们的强乘积的分数色数和色数进行估计.     

图的分数着色和分数色数

引入了一种新的图着色 :图的分数关联着色。定义了图的分数关联色数。讨论了分数关联着色的性质 ,给出了图的分数关联色数的一个下界。     

球面经纬线图的分数色数

图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用．本文给出了球面经纬线图以及它的r-冠图的分数色数,分数关联色数和分数全色数．     

循环图的星色数与分数色数

给出了循环图的星色数等于分数色数的一个充分条件。     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

不含特殊短圈平面图的无圈边染色

无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了：如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ（G）＋1.     

一些平面图的无圈边染色

主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。     

几类图的2-强边染色

研究了树、圈、完全二部图和轮图的2-强边染色问题.对于树,给出了2-强边色数等于最大顶点度加1的充分条件;对于圈、完全二部图及轮图,求出了2-强边色数,并给出了相应的染色方案.     

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

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

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

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

△（G）=4的图的强边染色

针对1985年Erdǒs和Nesetǐil提出的强边一染色猜想：令G为图,若△（G）为偶数,则Sx’（G）≤5△^2（G）／4;若△（G）为奇数,则Sx’（G）≤5△^2（G）／4-A（G）／2＋1／4。证明了对于令G为△（G）=4的图,若δ（G）≤3或围长g（G）≤4,则Sx’（G）≤21。     

若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).