CAJ | 학술논문

设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色数Xb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得Xb(G,T)=4.
설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색수Xb(G,H)위최소적정수k,사득(G,H)시BB-k가염적.본문연구료대우임의적련통,비이부평면도G,차G몰유5-권,도존재일과생성수T,사득Xb(G,T)=4.
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.