重图的超f - 边覆盖染色

图G的一个超f - 边覆盖染色就是它的一个f - 边覆盖染色并且使得图G中的重边染上不同的颜色. 令χ^H_fc(G)是图G存在一个超f - 边覆盖染色时所需最大的颜色数k. χ^H_fc(G)称作是图G的超f - 边覆盖染色色数. 本文讨论重图的超f - 边覆盖染色的存在性并且给出了重图的超f - 边覆盖染色的色数下界.     

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.     

平面图和系列平行图的无圈边染色

图$G$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)\leq{\Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)\geq3$, 则$a''(G)\leq\max\{2\Delta(G)-2,\Delta(G)+22\}$; 如果 $g(G)\geq5$, 则$a''(G)\leq{\Delta(G)+2}$; 如果$g(G)\geq7$, 则$a''(G)\leq{\Delta(G)+1}$; 如果$g(G)\geq16$并且$\Delta(G)\geq3$, 则$a''(G)=\Delta(G)$; 对系列平行图$G$, 有$a''(G)\leq{\Delta(G)+1}$.     

图的因子和因子分解的若干进展

本文综述了图的的因子和因子分解近年来的一些新结果。主要有图的因子与各种参数之间的关系,图有某种因子的一些充分必要条件,特别是图有ｋ－因子的一些充分条件以及关于图的因子分解和正交因子分解的一些新结果。文中提出了一些新的问题和猜想。     

4一致(ξ)-超图的最小边数的上界

主要讨论了4一致l-超图的最小边数与最小上色数的关系,给出了上色数为3的4一致l-超图的最小边数的一个上界.     

PROPERTIES OF FRACTIONAL k-FACTORS OF GRAPHS

In this paper the properties of some maximum fractional [0, k]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional k-factors is obtained.     

ON f-EDGE COVER-COLOURING OF SIMPLE GRAPHS

An f-edge cover-colouring of a graph G = (V, E) is an assignment of colours to the edges of G such that every colour appears at each vertex υ∈ V at least f(υ) times.The maximum number of colours needed to f-edge cover colour G is called the f-edge cover chromatic index of G, denoted by χfc(G). This paper gives that min[d(ν)-1/f(ν)] ≤χfc(G) ≤min[d(υ)/f(υ)].     

FRACTIONAL (g, f)-FACTORS OF GRAPHS

1 IntroductionThe graphs considered in this paper will be finite undirected graphs wllicll 11lay llavemultiple edges but no loops. Let G be a grapll with vertex set V(G) and edge set E(G). Fora vertex x of G, the degree of x in G is denoted by dG(z). Let g and f be two integer-valuedfunctions defined o11 V(G) such that 0 < g(z) 5 f(x) fOr all x E V(G). Then a (g, f)-factorof G is a spanning 8ubgraph F of G satisfying g(x) < dG(z) 5 f(x) for all x E V(F). Ifg(x) = f(x) for all x E V(…     

图的（g＜f）－因子

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数且ｇ＜ｆ．本文给出了过图的每条边有一个（ｇ，ｆ）－因子的新的简单的判断准则，并研究了它的应用。从而得到了一些关于图有（ｇ，ｆ）－因子的新的充分条件，推广了若干已有的结果．     

组合拓扑方法在组合学和图论中的应用

本文介绍组合拓扑方法在图论和组合学中的应用，探索一些新的离散问题和连续问题的关系，介绍目前有关这方面的新结果及发展动向。本文主要介绍同调理论在图论中的应用，与图有关的复形及性质，不动点定理在离散问题中的应用等。文中提出了一些新结果及可供研究的新问题。