首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 125 毫秒
1.
如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.  相似文献   

2.
关于完全图的Mycielski图的循环色数的若干结果   总被引:5,自引:0,他引:5  
刘红美  聂晓冬 《数学研究》2004,37(4):407-416
给出了任意图G的多重Myeielski图M^m(G)的简单定义方式,用不同的方法证明了当完全图Kn的阶数n足够大时,M^m(Kn)的循环色数等于其点色数.特别证明了,n=7,8,9时,M^3(Kn)的循环色数等于其点色数,从而使得“当n≥m 2,有xc(M^m))=x(M^m(Kn))=m n成立”的猜想有了更新的进展.  相似文献   

3.
用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.  相似文献   

4.
用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的.  相似文献   

5.
早在上世纪五十年代,Zarankiewicz猜想完全2-部图Km,n(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数).目前这一猜想的正确只证明了当m≤6时成立.本文主要证明了若Zarankiewicz猜想对m=7成立,则完全3-部图K1,6,n的交叉数为9[n/2][n-1/2] 6[n/2].  相似文献   

6.
设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.  相似文献   

7.
尹建华  李炯生 《应用数学》2002,15(1):123-128
设σ(k,n)表示最小的正整数m,使得对于每个n项正可图序列,当其项和至少为m时,有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想:σ(k,n)=(k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5,n≥(^k2))+3是对的,并且提出如下问题:确定最小的整数N(k),使得这个猜想对于n≥N(k)成立。他们同时指出:当k≥5时,[5k-1/2]≤N(k)≤(^k2) 3.Mubayi猜想:当k≥5时,N(k)=[5k-1/2]。在本文中,我们证明了N(8)=20,即Mubayi猜想对于k=8是成立的。  相似文献   

8.
张丽  陈东灵  陈学刚 《数学进展》2006,35(2):171-177
本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1.同时还研究了树和完全二部图的Mycielski图的关联色数.文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图.  相似文献   

9.
完全3-部图K_(1,10,n)的交叉数   总被引:1,自引:0,他引:1  
在上世纪五十年代初,Zarankiewicz猜想完全2-部图Km,m(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数),目前只证明了当m ≤ 6时,Zarankiewicz猜想是正确的.假定Zarankiewicz猜想对m=11的情形成立,本文确定完全3-部图K1,10,n的交叉数.  相似文献   

10.
关于图的点可区别边染色猜想的一点注   总被引:1,自引:0,他引:1  
图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确.  相似文献   

11.
Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.  相似文献   

12.
最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.  相似文献   

13.
A graph G is said to be chromatic-choosable if ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K3*2,2*(k-3),1, K3,2*(k-1), and Ks+3,2*(k-s-1),1*s. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K4,3,2*(k-4),1*2 and K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al.  相似文献   

14.
Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.  相似文献   

15.
The cycle length distribution of a graph G of order n is a sequence (c1 (G),…, cn (G)), where ci (G) is the number of cycles of length i in G. In general, the graphs with cycle length distribution (c1(G) ,…,cn(G)) are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution (c1 (G),…, cn (G)) is unique. Let Kn,n+r be a complete bipartite graph and A lohtaib in E(Kn,n+r). In this paper, we obtain: Let s 〉 1 be an integer. (1) If r = 2s, n 〉 s(s - 1) + 2|A|, then Kn,n+r - A (A lohtain in E(Kn,n+r),|A| ≤ 3) is determined by its cycle length distribution; (2) If r = 2s + 1,n 〉 s^2 + 2|A|, Kn,n+r - A (A lohtain in E(Kn,n+r), |A| ≤3) is determined by its cycle length distribution.  相似文献   

16.
Abstract Let Kv be the complete graph on v vertices, and G a finite simple undirected graph without isolated vertices. A G-packing of Kv, denoted by (v, G, 1)-packing, is a pair (X,A) where X is the vertex set of K+ and +4 is a family of edge-disjoint subgraphs isomorphic to G in Kv. In this paper, the maximum number of subgraphs in a (v, G, 1)-packing is determined when G is K2 x K3, the Cartesian product of K2 and K3, leaving two orders undetermined. This design originated from the use of DNA library screening.  相似文献   

17.
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.  相似文献   

18.
设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.  相似文献   

19.
For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.  相似文献   

20.
一类几乎唯一泛圈图   总被引:2,自引:0,他引:2  
设G是阶为n的简单Hamilton图.若存在m(3(?)m相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号