共查询到20条相似文献,搜索用时 93 毫秒
1.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献
2.
3.
4.
关于图的均匀全色数分类 总被引:1,自引:0,他引:1
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数. 相似文献
5.
对圈、扇和轮作了简单的剖分,得到了其剖分图的星全色数,并运用Lovasz局部引理证明了若G(V,E)是一个最大度为△≥3的简单无向图,则Χ_(st)(G)≤22Δ~2. 相似文献
6.
对于图G(V,E)的正常k-全染色φ称为G(V,E)的k-均匀全染色,当且仅当任意两个色类中的元素总数至多相差1.xvee(G)=m in{k存在图G的一个k-均匀全染色}称为G的均匀全色数.本文得到了两类M ycielsk i图及圈,轮图和扇形的均匀全色数. 相似文献
7.
对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若满足:1)uv,uω-∈E(G),v≠,-ωf(uv)≠f (uω-);2)uv∈E G,C(u)≠C(v).则称f是G的点关联邻点可区别全染色法,其所用到的最少颜色数称为图G的点关联邻点可区别全色数.这里C(u)=f(u)∪f(uv)uv∈E(G).得到了扇和轮的倍图的点关联邻点可区别全色数. 相似文献
8.
9.
图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数. 相似文献
10.
11.
12.
The total chromatic number XT(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if XT(G)=Δ(G) 1. In this paper we prove that the join of a complete bipartite graph Km,n and a cycle Cn is of Type 1. 相似文献
13.
提出了图的D(β)点可区别星边染色及D(β)点可区别星边色数的概念,并用Lovasz局部引理证明了在β=2时,若G=(V,E)是一个最小度为δ(G)>3的简单无向图,则X_(2-vds)(G)≤24△2/3]。 相似文献
14.
关于图的星色数的一点注记 总被引:1,自引:0,他引:1
A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored.The star chromatic number of an undirected graph G,denoted by χs(G),is the smallest integer k for which G admits a star coloring with k colors.In this paper,we show that if G is a graph with maximum degree △,then χs(G) ≤ [7△3/2],which gets better bound than those of Fertin,Raspaud and Reed. 相似文献
15.
完全二部图广义Mycielski图的邻点可区别全色数与邻强边色数 总被引:6,自引:1,他引:5
得到了完全二部图Km,n的广义Mycielski图Ml(Km,n),当(l≥1,n≥m≥2)时的邻点可区别全色数与邻强边色数. 相似文献
16.
Bing Zhou 《Journal of Combinatorial Theory, Series B》1997,70(2):245-258
We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number. 相似文献
17.
Michael Molloy 《Journal of Graph Theory》2017,84(1):53-56
We prove that the adaptable chromatic number of a graph is at least asymptotic to the square root of the chromatic number. This is best possible. 相似文献
18.
Butenko S. Festa P. Pardalos P. M. 《Journal of Optimization Theory and Applications》2001,109(1):69-83
In this paper, the property of a function to be without exceptional family of elements (EFE) is investigated. We show that, for a pseudomonotone operator, the solvability of a complementarity problem is equivalent to the property of the function to be without EFE. Finally, we study the strict feasibility of a complementarity problem making use of the Leray-Schauder alternative and the notion of EFE. 相似文献
19.
Let Dn be the dihedral group of order 2n. Denote by E(Dn) (resp. A(Dn), I(Dn)) the distributively generated nearring generated by the set of all endomorphisms (resp. automorphisms, inner automorphisms). In this paper, we determine for each one of the above three nearrings a minimal (additive) generating set. For E(Dn), this set contains the identity mapping and four other endomorphisms; for A(Dn), the identity mapping, one outer automorphism and one inner automorphisms; and for I(Dn), the identity mapping and two inner automorphisms. 相似文献