ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

1 IntroductionIn this paper we con8ider finite undirected simple graphs. Let G be a graph with vertexset V(G) and edge set E(G). Let g and f be two po8itive iuteger-valued functions defined onV(G) such that g(x) 5 f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanningsubgraph H of G satisfying g(x) 5 dH(x) 5 f(x) for each x E V(H). In particular, if G itselfis a (g, f)-factor, then G is called a (g, f)-grapl1. A subgrapl1 H of G is called an rmsubgraphif H has m edg…     

图的分数k-因子

给定图G=(V,E).设a和b是两个非负整数.fE→［0,1］是一个函数.如果     

（mg＋k,mf—k）—图中正交于r个不相交子图的边不变的（g,f）—因子

设m,k和r为正整数,且使l≤k＜m.设G是一个具有顶点集合V(G)和边集合E(G)的图,并设g和f是定义在V(G)上的使对每个x∈V(G)有r≤g(x)≤f(x)的整数值函数.设H1,H2,…,Hr是G的r个顶点不相交的子图且|E(Hi)|=k,1≤i≤r.本文证明了每个(mg+k,mf-k)-图有k个边不相交的(g,f)-因子正交于Hi,1≤i≤r.     

无圈超图的1—因子定理

本文证明了一个无圈超图 H=(X,E)有1-因子当且仅当(?)S(?)X,sum from i=1 to r-1(r-i)q_i≤|S|,其中 q_i 表示 H 的子超图 H-S 的顶点数模 r 等于 i 的连通分支数,r 是超图 H 的秩.     

图有分数因子的度条件

本文研究了图有分数因子的度条件,得到了下面的结果：令k(?)1是一个整数,G是一个连通的n阶图,n(?)4k-3且最小度δ(G)(?)k,若对于每一对不相邻的顶点u,v∈V(G)都有max{d_G(u),d_G(v)}(?)n/2,则G有分数k-因子．并指出该结果在一定意义上是最好可能的。     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

3一致 C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k 1时,该下界是可以达到的．     

开集与色树理论

Ｗｈｉｔｎｅｙ和Ｔｕｔｔｅ为了探讨四色问题的理论证明曾把平面四色问题与圈上的４染色集的性质联系起来进行研究，提出了开集的概念和色树理论。本文研究圈上４染色集的性质，证明开集在某种组合运算后仍为开集，从而发展了色树理论，为研究平面图的染色问题提供了新的方法。文末提出了一些进一步研究的问题。     

（mg,mf）—图中具有特殊性质的（g,f）—因子

本文给出了一类带有边连通度限制的（ｍｇ,ｍｆ）－图有一个（ｇ,ｆ）因子含任一给定的边且不含其它任意给定的ｍ－１条边的一个充分必要条件,并使（１）中结果成为本文定理的推论。     

图中相互独立的4圈和含4个点的路

设k是一个正整数,G是一个顶点数为|G|=4k的图. 假设σ-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的. 设G=(V-1,V -2;E)是一个二分图使得|V-1|=|V-2|=2k. 如果对G中每一对满足x∈V-1和y∈V-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的,并且此度条件是最好的.