全着色边临界图的一个注记

研究了全着色边临界图的结构，证明了对于△≥5的全着色边临界图G（V，E），若u∈V（G），d（u）=3，uvi∈E（G）（i=1，2，3），则△-1≤d（vi）≤△．     

关于图的非正常边着色

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

关于9—临界图边数的下界

本文给出了9－临界图边数的下界：m≥118／39n,其中n为点九，m为边数。     

混合图的边着色

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

8—临界图边数的下界

本文给出了８－临界图边数的下界。     

极小3-连通双临界图的点着色数

证明了极小3-连通双临界图的点着色数小于等于4.     

一类凯莱图的2—边临界性

设Г是奇数阶阿贝尔群上的４－正则连通凯莱图，讨论了Г－｛ｅ１，ｅ２｝的边着色问题，其中ｅ１，ｅ２是Г的任意两边，通过研究了Г的哈密顿分解，得出如下结果；对Г的任意两条边ｅ１，ｅ２，存在Г的一个哈密顿分解分离ｅ１，ｅ２；进而证明了Г－｛ｅ１，ｅ２｝是第一类的。     

图的广义边着色中一个不等式的证明

本文先证明下述不等式:设i,j,k,a皆为实数,其中a,k为常数,i+j=a,当|i_1—j_1|≤|i_2—j_2|时,有|k—i_1|+|k—j_1|≤|k—i_2|+|k—j_2|,再利用此不等式来证明图的广义边着色中的一个不等式。     

关于p阶临界h边连通图的一个注记

文［１－４］分别给出了ｐ阶临界２边连通图ｐ阶临界３边连通图以及ｐ阶临界ｈ（≥４）边连通图的最大边数及其结构。本文相应给出了ｐ阶临界ｈ（≥３）边连通图最大边数更为简捷的结果。可应用于改进和提高通讯网络的可靠性     

关于图划分中的一个计算复杂性问题

一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G中是否存在稳定集S使得G-S是一个仙人掌图.我们证明了STABLE CACTUS-问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung-树方法,证明了如果G是一个最大度不超过3的图,则STABLE CACTUS-问题是多项式时间可解的.     

关于图的和宽问题

设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G~C)≥2p(G)+2,p(G)=|V(G)|。     

图的一因子分解

本介绍了有关一因子分解的主要概念和主要结构，并举例说明这些定理条件的必要性，最后讨论一因分子解的一个猜想，给出了对这个猜想至今为止的所有结果并举例说明这猜想不是充分必要的。     

图的最长路的一个性质

本文给出了图的最长路的一个性质:设G是有n个点的2-连通图,如果对于任一对使d（u,v）=2的点u和v而推出max{d（u）,d（v）}≥c/2（3≤c≤n）,那么存在一条最长路μ=v_1v_2…v_r,且min{d（v_1）,d（v_r）}≥c/2。由此可得到图中圈长性质的一个较简单的证明。     

Hamilton图的一个注记

本文的主要结果是：设G是D－圈图,若存在某个t≤δ,使得对任何t＋1个点的独立集,X＝｛x0,x1,…,xz）,有,则G是Hamilton图。     

极大平面图对偶二色子图结构特性树

本文在论文[1]的基础上给出极大平面图的另外一种商图,即极大平面图对偶二色子图结构特性图.证明极大平面图对偶二色于图特性图是树,并给出它的若干性质.     

产生图的全部哈密顿回路

本文对完全图和非完全图分别给出了一个产生图中全部Hamilton回路的算法。与已有算法比较,本文提出的算法具有速度快、内存小的优点。该算法用于判别一个图是否Hamilton图效果良好。     

关于正则图的道路双覆盖猜想

［１］汇集了１９９０年国际图论会议（丹麦）上所提出的２７个新的未解决的问题，其中第一个就是关于正则图的道路双覆盖猜想，Ａｄｒｉａｎ Ｂｏｎｄｙ等人利用Ｐｅｔｅｒｓｅｎ定理已证明：对于３－正则图猜想为真。本文证明了对于任意的ｍ－正则的完全图，猜想是成立的。     

不含K3图的周长

设Ｇ为不含Ｋ３的２连通的非偶图的图。Ｄ（ｕ）｛ｖ｜ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝２｝，δ０＝ｍｉｎ｛ｍａｘ（ｄ（ｕ），ｄ（ｖ）｜ｕ，ｖ∈Ｖ（Ｇ）且ｄ（ｕ，ｖ）＝２｝，Ｄ（δ０）＝｛ｕ｜ｕ∈Ｖ（Ｇ）且ｄ（ｕ）≥δ０｝，δ≥δ０时还满；