具有大的奇围长的符号图的圆环染色（英文）

图G的一个圆环r-染色(r≥2)是将G的每个顶点v对应到一个周长为r的圆上的点的一个映射f,使得对于G中任意的边xy,f(x)和f(y)在圆上的距离不小于1.G的圆环色数χ_c(G)是G存在圆环r-染色的最小实数r.符号图的圆环染色和图的圆环染色基本相同,不同的是对于负边xy,我们要求f(x)和f(y)的对点在圆上的距离不小于1.符号图(G,σ)的圆环色数是使得(G,σ)在圆环r-染色的最小实数r.本文证明:对于任意正整数k和实数ε> 0,存在整数g使得对于任意树宽至多为k的符号图(G,σ),如果(G,-σ)的负围长至少是g,那么(G,σ)的圆环染色数至多是2+ε.     

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数.     

联图的关联着色

图G的一个κ-关联着色是指从G的关联集I(G)到颜色集{1,2,…,κ}的一个映射,满足任意一对相邻的关联分配到不同的颜色.使得G有κ-关联着色的最小的数κ称为G的关联色数,记为X_i(G).研究了联图的关联着色,给出了G∨H的关联色数的一个上界,讨论了路与路,路与圈,圈与圈的联图的关联色数.     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

Pm□Pn的Smarandachely-邻点可区别边色数

图G的正常边染色f满足相邻点的色集合相不互包含时,该染色称为图G的Smarandcchely-邻点可区别边染色,其中S(x)={f(xw)|xw∈E(G)}称之为在f下的顶点x的色集合.该染色称为图G的Smarandchely-邻点可区别边染色.对图G进行的.Smarandchely-邻点可区别边染色所用最少颜色数称为图G的Smarandachely-邻点可区别边色数.讨论了Pm□Pn的Smarandchely-邻点可区别边色数.     

Klein瓶上的6-正则嵌入图的着色性质

Brooks证明了:若G是连通的简单图,并且它既不是奇圈,又不是完全图,那么它的色数至多为△(G),其中△(G)为图G的最大度.它可以推出嵌入到Klein瓶上的任意的一个6-正则图的色数至多为6.通过对Klein瓶上的6-正则嵌入图的结构分析,证明了Klein瓶上的任意的一个6-正则嵌入图的色数为5.     

k-方图的邻点可区别无圈边染色

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_^(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数.     

含有大的悬挂树图的Ramseygoodness结论(英文)

设H是阶为n的连通图.在H的某一个顶点上悬挂一棵阶为j的树,得到图H_j,用H_j表示这样的图形族.本文证明:当j充分大时,有r(G,H_j)=(x(G)-1)(n+j-1)+s(G),其中x(G),s(G)分别表示图G的色数和色数剩余.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

图和色多项式根2的阶

本文证明了3-连通非偶图的色多项式根2的阶为1;满足一定条件的非3-连通非偶图的色多项式根2的阶是图的非偶块和非偶可分块数.从而,把色多项式P(G)中1的阶是图G的非平凡块数这一结果进一步加以推广.     

CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M(G) denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number Xc(M(G)) equals to the chromatic number X(M(G)), which have improved some best sufficient conditions published up to date.     

图的（k，d）-着色问题的一个近似算法

本文讨论了图的(k,d)-着色问题的算法,并给出了一个由四层神经元组成的神经网络算法.当一个图的循环色数已知时(不妨设为k/d),可以利用该算法成功地求出这个图的一个可行(k,d)-着色方案;当一个图的循环色数未知时,可以利用该算法求出这个图的循环色数的近似值.     

超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色

Mycielski图是在1955年由Mycielski首先提出的,推广的Mycielski图是在2003年由Peter Che Bor Lam,林文松等给出的Mycielski图的一个自然推广,且研究了它的圆色数.目前关于推广的Mycielski图性质以及它们在点色数,分数色数,圆色数等方面已有许多研究.本文定义了推广的Mycielski图的另一推广称为类推广的Mycielski图,且探讨了推广的Mycielski图和类推广的Mycielski图在全染色、邻点可区别全染色方面与原基础图的关系,从而也得到了它们满足全染色猜想和邻点可区别全染色猜想及它们达到全色数和邻点可区别的全色数的下界的一些充分条件.     

Coloring graphs by translates in the circle

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.     

Circular choosability is rational

The circular choosability or circular list chromatic number of a graph is a list-version of the circular chromatic number, that was introduced by Mohar in 2002 and has been studied by several groups of authors since then. One of the nice properties that the circular chromatic number enjoys is that it is a rational number for all finite graphs G, and a fundamental question, posed by Zhu and reiterated by others, is whether the same holds for the circular choosability. In this paper we show that this is indeed the case.     

平面图的循环色数及临界性

循环着色是普通着色的推广．本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的．同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件．     

关于扇和完全等二部图联图的均匀全色数

对于一个正常的全染色满足各种颜色所染元素(点和边)数量的和相差不超过1时,称为均匀全染色,其所用最少的染色数称为均匀全色数.本文得到了m+1阶扇Fm和完全等二部图Kn,n的联图Fm∨Kn,n的均匀全色数.     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

Density and power graphs in graph homomorphism problem

We introduce two necessary conditions for the existence of graph homomorphisms based on the concepts of density and power graph. As corollaries, we obtain a lower bound for the fractional chromatic number, and we set forward elementary proofs of the facts that the circular chromatic number of the Petersen graph is equal to three and the fact that the Coxeter graph is a core.