| 没有5-圈的平面图的BB-染色 |
| |
| 引用本文： | 张水明,卜月华.没有5-圈的平面图的BB-染色[J].数学研究,2010,43(4):315-321. |
| |
| 作者姓名： | 张水明 卜月华 |
| |
| 作者单位： | 浙江师范大学数理与信息工程学院; |
| |
| 基金项目： | supported by the National Natural Science Foundation of China(10971198); the Natural Science Foundation of Zhejiang Province(Y607467). |
| |
| 摘 要： | 设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.
|
| 关 键 词： | BB-染色 生成树 可平面图 |
Backbone Coloring for C5-free Planar Graphs |
| |
| Zhang Shuiming,Bu Yuehua.Backbone Coloring for C5-free Planar Graphs[J].Journal of Mathematical Study,2010,43(4):315-321. |
| |
| Authors: | Zhang Shuiming Bu Yuehua |
| |
| Institution: | Zhang Shuiming Bu Yuehua (College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua Zhejiang 321004) |
| |
| Abstract: | Let G be a graph and H a spanning subgraph of G.A backbone-k-coloring of (G, H) is a mapping f : V(G) → {1, 2, …, k} such that |f(u) - f(v)| ≥ 2 if uv ∈ E(H) and |f(u) - f(v)| ≥1 if uv ∈ 6 E(G)\E(H). The backbone chromatic number of (G,H) denoted by Xb(G, H) is the smallest integer k such that (G, H) has a backbone-k-coloring. In this paper, we prove that If G is a connected non-bipartite Cs-free planar graph, then there exists a spanning tree T of G such that Xb(G, T) = 4. |
| |
| Keywords: | Backbone coloring Spanning tree Planar graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
