Halin图的消圈数及点染色问题

Tutte关于3-连通图的结构定理表明:每一个3-连通图都可由某个轮图(也是Halin图)经顶点分裂逐步得到.这表明了Halin图在图结构研究中的地位和作用.首先研究得到了近正则Halin图的消圈数的上、下界并证明了上述界是紧的,接着得到了最大度为k或最小度为k的Halin图的消圈数所满足的界;此外还研究了Halin图的点染色问题,给出了它的点色数定理的一个新证明.     

3-正则Halin图的全色数

研究了△(G)=3时Halin图的全色数,证明了(i)对于3-正则的Halin图G,有4≤xT(G)≤5;(ii)若将3-正则Halin图每边剖分一次,则对于剖分图M*有xT(M*)=4,这里△(G)表示图G的最大度数,xT(G)表示图G的全色数.     

立方Halin图的完备色数

 证明了每个立方Halin图H是完备6可着色的,并且H有一个完备6-着色,使得每一种色出现在每一个面(顶点)以及与其相邻(关联)的顶点、边和面的着色集中。     

3-正则Halin图的剖分图的全色数

研究了3-正则Halin图的剖分图G的全色数,证明了4≤xT(G)≤5,特别是当G的3-度点彼此不相邻时,有xT(G)=4,这里xT(G)表示G的全色数.     

几种特殊图的均匀边染色

研究立方Halin图以及一些倍图的均匀边染色,利用换色法、构造法和归纳法得出：立方Halin图和路的倍图都是均匀的,星的倍图都有均匀4-边染色．     

关于图的邻和可区别全染色的新方法

给出树的邻和可区别2-全染色方案,并结合三正则图最小消圈集的独立性以及消圈子图的无圈性,较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。     

初等交换群凯莱图的完备码与完全图的正则覆盖

LEE证明了超立方体图Q_n存在完备码当且仅当n=2~m-1(m≥2是自然数),当且仅当它是完全图K_(n+1)的正则覆盖.本文中,给出了这个结论的一个简单证明,并把这个结论推广到了初等交换群的凯莱图中.证明了初等交换p-群Z_p~n(这里p是奇素数)的凯莱图有完备码当且仅当n=(p~m-1)/2 (这里m是自然数且n≥2),当且仅当它是完全图K_(2n+1)的正则覆盖.     

Halin图的有点面约束的边染色

研究了Halin 图的有点面约束的边染色,给出了Halin 图的有点面约束的边染色色数的一个精确结果.     

Halin图的一个点强全染色法

针对Halin图的点强全染色问题,提出一个有效的染色法———逐圈着色法,而且方法给出的方案也是最优的,即用最少的颜色完成Halin图的点强全染色.同时还确定了最大顶点度是3的Halin图的点强全色数的上下界,即上界为6,下界为5.     

若干类3-正则图的Smarandachely邻点全染色的界

针对3-正则图的结构性质,利用组合分析法和构造染色的方法讨论了若干类3-正则图的Smarandachely邻点全染色,并得到了其Smarandachely邻点全色数,进一步验证了图的Smarandachely邻点全染色猜想.     

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成立.     

关于图的全荫度和列表全荫度的一些结果

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2].     

完全二部图K_(3,n)(3≤n≤17)的点可区别E-全染色

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

完全二部图K_(6,8)的点强可区别全染色

利用组合分析法,考虑完全二部图K_(6,8)的点强可区别全染色方案,给出一种可行的染色方案.结果表明,完全二部图K_(6,8)的点强可区别全色数为10.     

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

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

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色

考虑完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色.利用组合分析法、反证法及构造染色的方法,给出一类特殊完全二部图的点可区别E-全染色.结果表明:当6≤n≤10时,K_(6,n)的点可区别E-全色数为5;当11≤n≤38时,K_(6,n)的点可区别E-全色数为6.