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

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

全色数与小阶路的混合Ramsey数

以χ２（Ｇ）记一图Ｇ之全色数，Ｐｎ表ｎ阶路，混合Ｒａｍｓｅｙ数χ２（ｍ，Ｐｎ）为最小正整数ｐ，对于每个ｐ阶图Ｇ，或者χ２（Ｇ）≥ｍ，或者ＧＰｎ。当ｍ取任意正整数、ｎ≤４时，本文得到χ２（ｍ，Ｐｎ）的确值     

关于全着色Ramsey数

以χ２（Ｇ）记一图Ｇ之全色数,全着色Ｒａｍｓｅｙ数χ２（ｍ,ｎ）为最小正整数ｐ,使得每一ｐ阶图Ｇ或有χ２（Ｇ）≥ｍ,或其补图Ｇ满足χ２（Ｇ）≥ｎ。本文给出χ２（ｍ,ｎ）的上、下界     

P_m∨P_n的全色数

图Ｇ的全色数ＸＴ（Ｇ）是使得Ｖ（Ｇ）Ｕ∪Ｅ（Ｇ）中相邻或相关联的元素均染不同颜色的最少颜色数目．如果ＸＴ（Ｇ）＝△（Ｇ）＋１，则记如果ＸＴ（Ｇ）＝△（Ｇ）＋２，则记Ｇ∈．两个图Ｇ和Ｈ的联图Ｇ∨Ｈ是一个简单图，使得Ｖ（Ｇ∨Ｈ）＝Ｖ（Ｇ）∪Ｖ（Ｈ），Ｅ（Ｇ∨Ｈ）＝Ｅ（Ｇ）∪Ｅ（Ｈ）∪｛ｕｖ（Ｇ），ｖ∈（Ｈ）｝．本文证明了对任意的两个正整数ｍ和ｎ，Ｐｍ∨Ｐｎ∈当且仅当ｍ＝ｎ＝２或ｍ＝ｎ＝１，从而完全确定了两个路的联图的全色数．     

图染色数的一个结果

图Ｇ的染色数Ｘ（Ｇ）是使得Ｇ中任何相邻两点均染不同色的最小颜色数。文中证明了，如果ω（Ｇ）≥６，△（Ｇ）＝ω（Ｇ）＋１，ㄧＶ（Ｇ）ㄧ≤２ω（Ｇ）＋１，则Ｘ（Ｇ）＝ω（Ｇ），给出了两个图Ｇ０，Ｇ１，使得ㄧＶ（Ｇ０）ㄧ＝１４，ω（Ｇ０）＝６，△（Ｇ０）＝７，Ｘ（Ｇ０）＝７；ㄧＶ（Ｇ１）ㄧ＝１１，ω（Ｇ１）＝５，△（Ｇ１）＝６，Ｘ（Ｇ１）＝６。     

图染色数的一个结果

图Ｇ的染色数Ｘ（Ｇ）是使得Ｇ中任何相邻两点均染不同色的最小颜色数．文中证明了：如果ω（Ｇ）≥６，△（Ｇ）＝ω（Ｇ）＋１，｜Ｖ（Ｇ）｜≤２ω（Ｇ）＋１，则Ｘ（Ｇ）＝ω（Ｇ），给出了两个图Ｇ０、Ｇ１，使得｜Ｖ（Ｇ０）｜＝１４，ω（Ｇ０）＝６，△（Ｇ０）＝７，Ｘ（Ｇ０）＝７；｜Ｖ（Ｇ１）｜＝１１，ω（Ｇ１）＝５，△（Ｇ１）＝６，Ｘ（Ｇ１）＝６．     

最大次为3且最大次点不相邻的图的全色数

图Ｇ的全色数ＸＴ（Ｇ）是使得Ｖ（Ｃ）ＵＥ（Ｃ）中相邻或相关联元素均着不同色的最少色数．若Ｇ的最大次点不相邻，△（Ｇ）＝３，则ＸＴ（Ｇ）＝４．     

Pn∨Pn的全色数

图Ｇ的全色数ＸＴ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）中相邻或相关的元素均染不同颜色的最少颜色数目。如果ＸＴ（Ｇ）＝△（Ｇ）＋１，则记Ｇ∈Ｃ１／Ｔ；如果ＸＴ（Ｇ）＝△（Ｇ）＋２，则记Ｇ∈Ｃ２／Ｔ。     

二面体群D_(2p)的出度为3的Cayley有向图的正规性

设Ｇ是一个有限群,Ｘ＝Ｃａｙ（Ｇ,Ｓ）是Ｇ关于Ｓ的Ｃａｙｌｅｙ有向图,称Ｘ关於群Ｇ是正规的,如果Ｇ的右正则表示Ｒ（Ｇ）在Ｘ的自同构群Ａｕｔ（Ｘ）中是正规的．设Ｄ２ｐ是２ｐ阶二面体群（ｐ为素数）,本文考察了Ｃａｙ（Ｄ２ｐ,Ｓ）（其中｜Ｓ｜＝３）关於Ｄ２ｐ的正规性,并给出了这些图的全自同构群．     

一些图的全着色计数

对给定图Ｇ,用Ｎ（Ｇ）代表使用ＸＴ（Ｇ）（指图Ｇ的全色数）种色对Ｇ的所有不同的正常全着色的数目．导出了路、星、长为３Ｋ的圈以及树的Ｎ（Ｇ）的计数公式     

图的圆色数等于其色数的充分条件

图G的圆色数xc（G）（也称为星色数）是图的色数的一种推广,给出了图的圆色数等于其色数的一些充分条件。     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.     

I(Cn)的圆色数

讨论了n-圈Cn的关联图I(Cn)的结构性质.证明了I(Cn)是4-正则的平面图并研究了其色数.主要研究I(Cn)的圆色数并得到结果:如果n=3m,则χc(I(Cn))=χ(I(Cn))=3;如果n=3m 2,则χc(I(Cn))=(6m 4)/(2m 1).当n=3m 1时,给出了χc(I(C3m 1))的一个界.     

一类距离图的分数色数

摘要：主要讨论了距离图G(Z,D_{m,k,k+1,k+2,k+3})(其中D_{m,k,k+1,k+2,k+3}=｛1,2,…,m｝-｛k,k+1,k+2,k+3｝)的分数色数,以及当2k≤m≤2k+5时G(Z,Dm,k,k+1,k+2,k+3)的色数。     

图的相邻强边着色数

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G) 1.     

外平面图的松弛竞赛色数

主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。     

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图，全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图，有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图，有x_T(G)=Δ(G)+1.