混合图的边着色

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

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

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

几类图的连续边着色

设G是简单图，用颜色1，2，3，…，对G的正常边着色，如果每一个顶点上表现的颜色都构成一个连续的整数集合，那么就称这个边着色是连续的，图G的亏度def（G）是粘在G上使它可连续边着色的悬挂边的最小数目，对几类图的亏度进行了研究。     

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

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

超级边连通r一致超图的充分条件

若一个连通图的任一最小边割一定是某个顶点的关联边集,那么称该图是超级边连通的.对超级边连通图的研究,不仅有理论意义,而且在网络可靠性的分析中也有广泛应用.超图是图的一个自然推广.论文将超级边连通性的概念推广到超图,给出超级边连通一致超图的最小度条件,并用例子说明所给的条件是紧的.所得结果是无向图相关结果的推广.     

关于平面图点荫度的一点改进

一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garev等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.     

超图圈偶边着色

本文根据N.Alon给出的一定范围内的圈偶边着色定义及色数定义,将其向超图上推广,得到了超图的最大偶边着色数。     

四类圈树的连续边着色

设G是简单图，用颜色1，2，3，…对G进行正常边着色，若每一个顶点上表现的颜色都能构成一个连续的整数集合，则称这个边着色是连续的．图G的亏度def（G）等于粘在G上使它可连续边着色的悬挂边的最小数目．文章研究了四类圈树的亏度．     

超图的最短路径算法

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

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

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

超图的谱研究

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

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

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

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

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

平面图的强边染色的一个结果

如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。     

图的各种一般全染色

图G的正常全染色是指若干颜色给G的顶点和边的分配,使任意2个相邻顶点、2条相邻边和任一顶点与它的关联边得到的颜色不同.将正常全染色的限制条件减弱,得到了各种一般全染色,并讨论了它们的色数.