两类冠图的点边邻点可区别全染色

 图的染色理论是图论的一个重要研究领域,求解图的色数被认为是一个NP-hard问题。对简单连通图G(V,E),存在一个正整数k,使得映射f :V(G)∪ E(G)→{1,2,…,K},如果对∀uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色(又称为邻点可区别VE-全染色),而χ_at^ve (G)=min{k|k－VE－AVDTC},称为G的点边邻点可区别边色数(又称为邻点可区别VE-全色数),其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。本文构造了两类冠图C_m·S_n和C_m·P_n,研究了两类冠图C_m·S_n和C_m·P_n的点边邻点可区别全染色。根据C_m·S_n和C_m·P_n的结构性质,用穷染递推的方法,得到了它们的相应色数,给出一种染色方案。

Vertex-edge Adjacent Vertex-distinguishing Total Chromatic Number of the Two Kinds of Crown Graphs

Graph coloring is one of the chief topics in the graph research, the solution of the chromatic number of the graph is an NP-hard problem. Let G(V, E) be a simple graph, k is a positive integer. f is a mapping from V(G)∪ E(G) to {1, 2, …, k} such that ∀uv∈E(G), then f(u)≠f(uv), f(v)≠f(uv), C(u)≠C(v), f can be called the vertex-edge-adjacent vertex distinguishing total coloring of G (adjacent vertex distinguishing VE-total coloring of G), χ_at^ve(G)=min{k|k－VE－AVDTC} would be called the vertex-edge-adjacent vertex distinguishing total chromatic number of G (adjacent vertex distinguishing VE-total chromatic number of G), where vertex-edge-adjacent vertex distinguishing total coloring of G C(u)={f(u)}∪{f(uv)|uv∈E(G)}. In this paper, two kinds of crown graphs C_m·S_n and C_m·P_n are designed, the vertex-edge-adjacent vertex distinguishing total coloring of C_m·S_n and C_m·P_n are studied. According to the properties of two kinds of crown graphs C_m·S_n and C_m·P_n, by using colors one by one and in recursion, the vertex-edge-adjacent vertex distinguishing total chromatic numbers of two kinds of crown graphs C_m·S_n and C_m·P_n are obtained.