摘要
图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)的最大度.
A proper k-total coloring f of the graph G(V, E) is said to be a k-vertex strong total coloring if and only if for every v ∈ V(G), the elements in N[v] are colored with different colors, where N[v] =. {u|uv E V(G)} ∪{v}. The value xT^vs(G) = min{k| there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G(V, E), if the graph obtained from G(V, E) by deleting all the edges on the boundary of a face f0 is a tree, then G(V, E) is called a Halin-graph. In this paper, xT^vs,8(G) of the Halin-graph G(V,E) with A(G) 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows: Let G(V, E) be a graph with the order of each component are at least 6, then xT^vs(G) ≤ △(G) + 2, where A(G) is the maximum degree of G.
基金
the National Natural Science Foundation of China (No.19871036) the Qinglan talent Funds of Lanzhou Jiaotong University
关键词
Halin-图
图染色
点强全染色
全染色
Italin-graph
coloring problem
vertex strong total coloring
total coloring problem.