共查询到20条相似文献,搜索用时 31 毫秒
1.
设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数. 相似文献
2.
Pm×Kn的邻点可区别全色数 总被引:6,自引:0,他引:6
设G是简单图.设f是一个从V(G)∪E(G)到{1,2,…,k}的映射.对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC).数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数.本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数. 相似文献
3.
设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联的边的颜色以及点x的颜色所构成的集合.若对任意uv∈E(G),有C(u)≠C(v),则称.f是图G的一个邻点可区别全染色.对一个图G进行邻点可区别全染色所需的最少的颜色的数目称为G的邻点可区别全色数,记为Xat(G).用C_5∨K_t表示长为5的圈与t阶完全图的联图.讨论了C_5∨K_t的邻点可区别全色数.利用正多边形的对称性构造染色以及组合分析的方法,得到了当t是大于等于3的奇数以及t是偶数且2≤t≤22时,X_(at)(C_5 V K_t)=t+6,当t是偶数且t≥24时,X_(at)(C_5 V K_t)=t+7. 相似文献
4.
设 $G$ 是一个简单图. 设$f$是从$V(G) \cup E(G)$到 $\{1, 2,\ldots, k\}$的一个映射.对任意的 $v\in V(G)$, 设$C_f(v)=\{f(v)\}\cup \{f (vw)|w\in V(G),vw\in E(G)\}$ . 如果 $f$ 是一个 $k$-正常全染色, 且对 $u, v\in V(G),uv\in E(G)$, 有 $C_f(u)\neq C_f(v)$, 那么称 $f$ 为$k$-邻点可区别全染色 (简记为$k$-$AVDTC$). 设 相似文献
5.
Xiang-en Chen Zhong-fu Zhang 《应用数学学报(英文版)》2008,24(1):55-58
In a paper by Zhang and Chen et al.(see [11]), a conjecture was made concerning the minimum number of colors Xat(G) required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat(G) and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G (the degrees of the vertices in the boundary of exterior face of G are all three) gives a tree. 相似文献
6.
7.
8.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献
9.
提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标.并据此提出猜想. 相似文献
10.
李晓东 《数学的实践与认识》2001,31(3):347-350
图的全染色是染色理论的重要内容 ,全染色猜想 :设 G是一个简单图 ,则 XT( G)≤△ ( G) +2是一个至今未解决的问题 .本文证明了对于一些图类全染色猜想是正确的 . 相似文献
11.
图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}.χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数.对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图.本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度. 相似文献
12.
WOODALL Douglas R 《中国科学A辑(英文版)》2009,52(5):973-980
It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles. 相似文献
13.
关于图的均匀全色数分类 总被引:1,自引:0,他引:1
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数. 相似文献
14.
15.
强会英 《数学的实践与认识》2012,42(7):244-249
对简单图G(V,E),存在一个正整数κ,使得映射f:V(G)U E(G)→{1,2…,κ},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,且称最小的数κ为图G的邻点可区别VE-全色数,讨论了路、圈、星、扇、轮等一些图的倍图与Mycielski图的邻点可区别VE-全色数。 相似文献
16.
设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数. 相似文献
17.
邻点可区别全染色猜想得到了国内外许多学者的关注和研究.迄今为止,这个猜想没有得到证明,也没有关于这个猜想的反例.叉连图对邻点可区别全染色猜想成立给予了证明,并给出了精确值.同时,证明了:存在无穷多个图,它们中的每一个图H至少包含一个真子图HH~1,使得x_as~″(H~1)x_as~″(H). 相似文献
18.
19.
Jonathan Hulgan 《Discrete Mathematics》2009,309(8):2548-2550
Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χat(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χat(G) when G is a complete graph or a cycle. 相似文献
20.
本文.证明了,当n≥2时,Xat(K_n×K′_n)=2n;当p,q≥2时,Xat(C_(2p)×K_(2q))=2q 3,其中K_n×K′_n是两个不同标号完全图的积图,C_(2p)×K_(2q)是偶圈和偶阶完全图的积图. 相似文献