图的（g＜f）－因子

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

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.     

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(…     

ON (g, f)-COVERED GRAPHS

A graph G is (g,f)-covered if each edge of G belongs to a (g,f)-factor. In this paper a necessary and sufficient condition for a graph to be (g,f)-covered is given.     

关于Whitney和Tutte猜想

ｗｈｉｔｎｅｙ和Ｔｕｔｔｅ把平面四色问题化为只与圈上的４染色集有关的问题来研究，从而探讨四色问题的理论证明；提出了一个蕴含着四色定理的猜想。本文研究开集的组合不变性，从而证明Ｗｈｉｔｎｅｙ和Ｔｕｔｔｅ的猜想不成立。     

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

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

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(υ)].     

直径为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-完全的.     

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

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