混合多重图的边着色

著名学者Daniel Král. ,Jan Kratochvil, Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bounded degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的,所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,本文作者着力研究混合多重图的边着色。     

完美C-超图的一个充分条件

混合超图是含有两种超边的超图，一种称为D-超边，一种称为C-超边，它们的区别主要体现在着色要求上．在任一着色中，要求每一D-超边至少有两个点着不同的颜色，每一C-超边至少有两个点着相同的颜色．只含D-超边的超图称为D-超图，只含C-超边的超图称为C-超图．主要讨论了C-超图的完美性问题，给出了完美C-超图的一个充分条件．     

C-完全一致混合超图不可着色的充要条件

混合超图H′=(X,Xl,mX-D0)(其中D0表示若干恰由X中m个元素组成的D-超边的集合)的着色与其顶点个数有着必然的联系,当顶点个数超过一定数量时,H′便不可着色.本论文给出并证明了这类超图不可正常着色的一个充要条件.这一结论也揭示了这类混合超图可正常着色时,其可拥有的最大顶点个数与它的恰由X中m个元素形成的D-超边的个数之间的关系.     

图的星边色数的一个新的上界

图的着色问题是图论中的一个重要问题,图论领域的诸多学者研究了图的各种着色.运用Lovsz局部引理,研究了图的星边着色(图G的星边着色是G的一个正常的边着色,并且使得G中无长为4的路是2-边着色的;图G的星边色数是G的所有星边着色中所使用的最小颜色数,记为χ’se(G)),并证明了最大度为Δ(Δ≥2)的简单无向图G的星边色数新的上界为χ’se(G)≤「9(Δ-1)3/2?.     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。     

关于边着色临界图的一个问题

H.P.Yap在[1]中提出这样一个问题,是否存在偶阶边着色8临界图,它除了有一个2度点和两个3度点外其余的都是8度点?作为本文定理推论的一个特殊情形给出了这个问题的否定性答案。     

超图的子图特征值的研究

研究了偶一致超图的子图邻接张量的特征值,首先利用其最大特征值得到超图边割的下界,并证明这个界是紧的,指出当且仅当2个子图均为正则超图时下界成立,其次证明了k一致超图是正则超图的充要条件为全1向量是其邻接张量的H-特征向量,这是图谱理论中的相关性质在超图的推广.     

Halin图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立，且当Δ≤4时，其色数不超过5；当Δ≥5时，其色数等于最大度。     

几类3-圈图的连续边着色

设G是简单图，用颜色1，2，3，…对G的边正常着色，如果每一顶点表现的颜色构成一个连续的整数集合，那么就称这个连着色是连续的，G的亏度就是加在G上使它可连续边着色的悬挂边的最小数目。本文给出了几类3-圈图的亏度并且讨论了它的连续边着色。     

关于图的非正常边着色

图Ｇ的非正常边着色，即（ｍ·ｄ）一边着色是把边集Ｅ（Ｇ）划分成ｍ个子集Ｅ１，Ｅ２，…，Ｅｍ，使得每一边子集的导出子图Ｇ〔Ｅｉ〕，ｉ＝１，２，…，ｍ的最大度最多是ｄ。Ｗｏｏｄａｌ问：对奇数ｄ和自然数ｍ，最大度是ｍｄ的第二类图中哪些是（ｍｄ）一边可着色的？哪些不是？本文对Ｗｏｏｄａｌ的这一公开问题给出了一些明确的解答。     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

超图的谱研究

本文简要介绍超图的矩阵谱与张量谱理论的近期主要成果,给出了超图的各种矩阵表示,以及各种矩阵谱与超图参数之间的关系。介绍了张量的概念,以及用k阶张量表示k －一致超图的三种方式,定义张量的H －特征值和Z－特征值,用两种特征值描述超图的性质。     

D-完全一致混合超图上色数的研究

混合超图的上、下色数与C-超边和D-超边数有着必然联系.一般地,增加C-超边会使下色数χ（H）增加,增加D-超边会使上色数χ-（H）减小.本论文对D-完全一致混合超图的上色数进行了研究,并得到一些初步的结果.     

无向超图的计数级数

应用置换群理论，引入了超边群，超图群和超图同构的概念，导出了超边群及其循环指标的一般表达式，导出了无向无标号标图和标号超图的计数级数，解决了无向超图的同构和计数问题。     

超图的分数着色和分数团

超图是最一般最复杂的离散结构,是图的自然推广,但是图中的一些定义和结论并不是都能轻而易举地推广到超图中.给出超图分数着色和分数团的定义,这与特殊情形下的图的分数着色和分数团的定义是相容的,并将图的分数着色和分数团的一些结论在超图中进行了推广.     

无圈超图的一个充分必要条件

引入植树超图的概念,利用植树超图给出了一个超图是无圈超图的充分必要条件.建立了无圈超图与树的对应关系,表明信息科学家提出的无圈超图与数学家建立的无圈图有着密切的联系,所得结果进一步刻画了无圈超图概念中"无圈"的本质.     

2K2∨K1冠图的一般点可区别全染色

借助星的一般点可区别全染色, 讨论2K₂∨K₁冠图的一般点可区别全染色. 在星的一般点可区别全染色下, 采用将星悬挂边的颜色由小到大依次排列, 最终扩展为2K₂∨K₁冠图的一般点可区别全染色的方法, 确定冠图依赖于悬挂边数目的一般点可区别全色数.