Halin图的集染色 |
| |
引用本文: | 万慧敏,苗连英. Halin图的集染色[J]. 达县师范高等专科学校学报, 2012, 0(2): 17-20 |
| |
作者姓名: | 万慧敏 苗连英 |
| |
作者单位: | 中国矿业大学理学院,江苏徐州221008 |
| |
基金项目: | 中央高校基本科研业务费专项基金(2010LKSX06) |
| |
摘 要: | 对于非平凡连通图G,G的k集染色是指映射c:V(G)→Nk,对任意顶点v∈V(G),定义邻色集cN(v)={c(u)|u∈N(v)},若对uv∈E(G)有cN(u)≠cN(v),则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs(G).为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G(Cp,Tq)的集色数是3,并且还证明了对任意的Halin图G(Cp,Tq),有p+1≤q≤2p-2成立.
|
关 键 词: | 集染色 集色数 完全图 Halin图 |
The Set Coloring of Halin Graphs |
| |
Affiliation: | WAN Hui - min, MIAO Lian - ying ( College of Science of China University of Mining and Technology, Xuzhou Jiangshu 221008, China) |
| |
Abstract: | For a non - trivial connected graph G, let c: V(G)---+Nk be a vertex coloring of G where adjacent vertices may be col- ored the same. For a vertex v of G , the neighborhood color set cN(v) is the set of colors of the neighbors ofv. The coloring c is called a k set coloring if cN(u) #cN(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number,x, (G) of G. It is proved that the set chromatic number of the Halin graph G( Co, Tq ) with p 34 is 3, and that for any a Halin graph G( Co, T ), there exists p + 1 q 〈2p - 2. |
| |
Keywords: | set coloring the set chromatic number complete graph Halin graph |
本文献已被 维普 等数据库收录! |
|