On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G(avsdtis the abbreviation ofadjacent-vertex-strongly- distinguishing total). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

AVDTC numbers of generalized Halin graphs with maximum degree at least 6

In a paper by Zhang and Chen et al.（see [11]）, a conjecture was made concerning the minimum number of colors Xat（G） required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat（G） and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G （the degrees of the vertices in the boundary of exterior face of G are all three） gives a tree.     

$P_mtimes K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)cup E(G)$ 到${1, 2,cdots, k}$的映射. 对每个$vin V(G)$, 令 $C_f (v)={f(v)}cup {f(vw)|win V(G), vwin E(G)}$. 如果 $f$是$k$-正常全染色, 且对任意$u, vin V(G), uvin E(G)$, 有$C_f(u)ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $chi_{at}(G)=min{k|G$ 有$k$-AVDTC}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

Pm×Kn的邻点可区别全色数

设G是简单图．设f是一个从V(G)∪E(G)到{1,2,…,k}的映射．对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}．如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC)．数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数．本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数．     

On coloring box graphs

We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n$n$-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n$n$-space has an admissible coloring with n+1$n+1$ colors. We show that for box graphs in n$n$-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}$\{1,2,3\}$, then the box graph is 3$3$-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 3$3$-colorable.     

图$P_mtimes P_n, P_mtimes C_n$ 和C_mtimes C_n$}的邻点可区别全色数的注记

设 $G$ 是一个简单图. 设$f$是从$V(G) cup E(G)$到 ${1, 2,ldots, k}$的一个映射.对任意的 $vin V(G)$, 设$C_f(v)={f(v)}cup {f (vw)|win V(G),vwin E(G)}$ . 如果 $f$ 是一个 $k$-正常全染色, 且对 $u, vin V(G),uvin E(G)$, 有 $C_f(u)neq C_f(v)$, 那么称 $f$ 为$k$-邻点可区别全染色 (简记为$k$-$AVDTC$). 设     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.