两类联图的全着色

一个图Ｇ＝（Ｖ，Ｅ）的一个ｋ－全着色是从Ｖ∪Ｅ到Ｉｋ＝｛１，２…ｋ｝上的一个映射ψ；如果对Ｖ∪Ｅ中任意两个相邻或相关联的元素ｅ１，ｅ２，都有ψ（ｅ１）≠ψ（ｅ２）时，则称ψ为Ｇ的一个正规全着色。图Ｇ的全色数定义为ｘＴ（Ｇ）＝ｍｉｎ｛ｋ｜存在Ｇ的一个正规ｋ－全着色｝。令Ｃｎ为ｎ个点的图，Ｋ↑－ｍ为ｍ个点的独立集，Δ为图的最大度。本文证明了在ｍ≠ｎ时联图Ｃｍ＋Ｃｎ的全色数为Δ＋１；在ｍ＋２〈ｎ或ｍ〉ｎ     

两类笛卡尔积图的关联色数

Ｒｉｃｈａｒｄ Ａ．Ｂｒｕａｌｄｉ和Ｊ．Ｑｕｉｎｎ Ｍａｓｓｅｙ在（１）中引入了图的关联色数,并且提出了关联色数猜想,即：每一个图Ｇ都可以用Δ（Ｇ）＋种色正常关联着色。本文的主要结果如下：我们不仅证明了路与路,路与圈的笛卡尔积图满足关联色数猜想,进而确定了它们的关联色数。     

图的色数问题研究

为了确定任意无向简单图Ｇ从分析点色数的出发，采用了作点集Ｖ的最小划分的方法，得到了一个点色数算法科给出了证明，从而解决了无向简单图的点色数问题。     

关于图的非正常边着色

图Ｇ的非正常边着色，即（ｍ·ｄ）一边着色是把边集Ｅ（Ｇ）划分成ｍ个子集Ｅ１，Ｅ２，．．．．，Ｅｍ，使得每一边子集的导出子图Ｇ（Ｅｉ），ｉ＝１，２，．．．，ｍ的最大度最多是ｄ。Ｗｏｏｄａｌｌ问：对奇数ｄ和自然数ｍ，最大度是ｍｄ的第二类图中哪些是（ｍｄ）一边可着色的？哪些不是？     

全制约数的上界

设Ｇ＝（Ｖ，Ｅ）是无孤立点的简单图．设Ｔ是Ｖ的子集，如对任意Ｕ∈Ｖ，存在ｕ∈Ｔ使得ｕｖ∈Ｅ，则称Ｔ为Ｇ的全制约集．全制约集的最小基数称为Ｇ的全制约数，记作γｔ（Ｇ）．本文证明了如Ｇ是阶数ｎ≥３，最小度至少为２的连通图，则γｔ（Ｇ）≤４「（ｎ＋ｌ）／７」     

k＋1色k—饱和图

给出了一类具有较多边数的ｋ＋１色ｋ＝饱和图（不含Ｋｋ，但添加任一边都含Ｋｔ的图）的结构。导出了ｎ点最大ｋ＋１色ｋ－饱和图的边数的下界。     

关于一类新的整和图

Ｈａｒａｒｙ 提出了整和图的概念,设 ｆ 为整数集到图 Ｇ（ Ｖ（ Ｇ） , Ｅ（ Ｇ）） 的顶点集 Ｖ（ Ｇ） 之间的一个单射,使得对于 Ｇ 的两个不同的顶点ｕ 和ｖ ,ｕｖ ∈ Ｅ（ Ｇ） ,当且仅当存在 ｗ ∈ Ｖ（ Ｇ） ,使 ｆ（ ｕ） ＋ ｆ（ ｖ） ＝ｆ（ ｗ ） ,则 Ｇ 称为整和图,并且他证 明了所有路 和星图是整 和图。树 中度数至少 为３ 的 顶点称为 叉点, Ｃｈｅｎ 用粘合法证明了广义星图和叉点距离至少为４ 的树是整和图,并同时猜测所有的树均为整和图。本文证明了所有叉点距离至少为３ 的树是整和图,从而给出了一类新的整和图     

关于一个猜想的简单证明

图Ｇ的一个（正常）路着色是一映射ψ：Ｖ（Ｇ）→Ｃ,使得Ｃ中任一元素的原象的导出子图是路的不交并,使Ｇ有正常路着色所需要的Ｃ的最小基数│Ｃ│,称为Ｇ的路色数,用ｘ（Ｇ;Ｐ∞）表示。Ｊ．Ａｋｉｙａｍａ和Ｅｒａ＾［３］提出如下问题：是否存在平面图Ｇ使得ｘ（Ｇ;Ｐ∞）＝４？关于这一问题,已有人证明＾［３,５］;对于任意平面图Ｇ,都有ｘ（Ｇ;Ｐ∞）≤３,这里我们从路色数的角度给出该问题的一个更简单的证明。     

交错群A5的3度Cayley图

设Ｇ是一个有限群，Ｓ是群Ｇ的一个不含单元元１的子集，则Ｇ的关于Ｓ的Ｃａｙｌｅｙ图Г＝Ｃａｙ（Ｇ，Ｓ）可由如下关系式定义Ｖ（Г）＝Ｇ，Ｅ（Г＝（ｇ，ｓｇ）／ｇ∈，ｓ∈Ｓ）给出３度Ｃａｙｌｅｙ图Г＝Ｃａｙ（Ａｓ，Ｓ），即／Ｓ／＝３时三个不同构类图的特征刻划，见定理１。     

2连通Hamilton图的一个充分条件

证明了如下结果：设Ｇ是阶为ｎ的２连通图，若对Ｇ中任一对距离为２的点ｕ，ｖ都有ｄ（ｕ）＋ｄ（ｖ）≥ｎ－１或｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｎ－δ，则Ｇ是Ｈａｍｉｌｔｏｎ图，除非Ｇ属于一个特殊图类。δ＝ｍｉｎｖ∈Ｖ（Ｇ）｛ｄ（ｖ）｝称为最小度。     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

The Incidence Coloring Number of Complete k-Partite Graph

The concept of the incidence chromatic number of a graph was introduced by Brualdi and Massey. Theyconjectured that every graph G can be incidence colored with △(G)+-2 colors. In this paper, the trueness of thisconjecture for complete k-partite graph was proved, and the incidence chromatic number of complete k-partitegraphs was calculated.     

Sm∨Fn的全色数

设G（V,E）是阶数至少是2的简单连通图,k是正整数,若厂是从V（G）∪E（G）到{1,2,…,k}的一个映射,使得：对于任意的uv,vw∈E（G）,u≠w,有f（uv）≠f（vw）;且对于任意的uv∈E（G）,u≠v,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,则称f为G的一个k-全染色（简记成k-TC of G）．而Xt（G）=min{k｜k—TC of G},称为G的全色数．设G和H是点边都不相交的简单图,V（G∨H）=V（G）∪V（H）,E（G∨H）=E（G）∪E（H）∪{uv｜u∈V（G）,v∈V（H）},则称G∨H是G与H的联图。给出m＋1阶星和n＋1阶扇的联图的全色数。     

关于色唯一图的注记

设P(G;λ)是图G的色多项式,如果对任意图H,当P(H;λ)=P(G;λ)时,都有H和G同构,则称图G是色唯一的。本文给出了由两个块H和K2构成的图G是色唯一的当且仅当H是色唯一点可迁的。     

双外平面图的全染色

双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图,V（G）,E（G）,F（G）分别为双外平面图G的点集,边集和面集。G的全色数XT（G）是使得V（G）UE（G）中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图,全色数是△（G）＋1,其中△（G）为G的最大度数。     

点可区别全色数的一个上界

设G是简单图,f是从V（G）UE（G）到{1,2,…,k）的一个映射．对每个u∈y（G）,令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果,是k-正常全染色,且对任意u,v∈V（G）（u≠v）,有c（u）≠c（v）,那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法,证明了对任意最大度A≥2的图G,χvt（G）≤32（△＋1）．     

图与其补图Q谱半径之和的上界

设G为n阶简单图,利用边数m,最小、最大顶点度δ和Δ以及色数k给出了G与其补图-G的Q谱半径之和的上界,当G不含孤立点时有:2(n-1)≤ρ(Q(G))+ρ(Q(-G))≤2(Δ-δ+n-1)和ρ(Q(G))+ρQ(-G))≤2n-3+2-12(n-1)n,其中t=min{k,-k}。当-G含l个孤立点时有:ρ(Q(G))+ρ(Q(-G))≤2n-3+2-1k(n-1)2+l,同时给出了图G与其补图-G的拉普拉斯谱半径之和的一个上界。     

不含四圈，三圈不重点的平面图全染色的一个结论

设G是一个图，Δ(G)是G的最大度.本文对3 圈不重点的，且不含从4到k圈的平面图，得出的结论有：如果(Δ,k)分别是（6，4），（5，5），（4，11），则G的全染色数是Δ(G)+1.     

图的全谐调着色数

图的全谐调着色数表示为Th(G)是相邻的点与边着不同颜色 ,且任何两个不同的边上有不同的三元颜色组的最小着色数。本文给出了关于图的全谐调着色数的各种定理     

图的范畴积的圆色数

图的圆色数的定义是图的色数的一个自然的推广,它是由Vince首先提出的.本文主要研究图的范畴积的圆色数.