关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

联图C_mVG_n的邻点可区别Ｅ-全染色(英文)

Let G（V, E） be a simple connected graph and k be positive integers. A mapping f from V∪E to {1, 2, ··· , k} is called an adjacent vertex-distinguishing E-total coloring of G（abbreviated to k-AVDETC）, if for uv ∈ E（G）, we have f（u） ≠ f（v）, f（u） ≠ f（uv）, f（v） ≠ f（uv）, C（u） ≠C（v）, where C（u） = {f（u）}∪{f（uv）|uv ∈ E（G）}. The least number of k colors required for which G admits a k-coloring is called the adjacent vertex-distinguishing E-total chromatic number of G is denoted by x^e_at （G）. In this paper, the adjacent vertexdistinguishing E-total colorings of some join graphs C_m∨G_n are obtained, where G_n is one of a star S_n , a fan F_n , a wheel W_n and a complete graph K_n . As a consequence, the adjacent vertex-distinguishing E-total chromatic numbers of C_m∨G_n are confirmed.     

圈和完全图的点可区别VE-全染色(英文)

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.     

关于图的一般邻点可区别全染色

提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标.并据此提出猜想.     

图的一般邻点可区别均匀边染色和一般邻点可区别均匀全染色

提出了 一般邻点可区别均匀边染色,一般邻点可区别均匀全染色的新概念,具体研究了路、圈、星、扇、轮、完全二部图、2维平面网格图Pm×Pn的一般邻点可区别均匀边染色和全染色,并给出这些图的一般邻点可区别均匀边染色指标和全染色指标.     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

仙人掌图的邻点被扩展和可区别全染色

设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称■为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi_∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的.     

没有K4-图子式的图的邻点可区别全染色

图 $G$ 的邻点可区别全染色是$G$ 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. $G$的邻点可区别全色数$chi''''_{a}(G)$是使得$G$有一个$k$-!邻点可区别全染色的最小的整数$k$. 本文完整刻画了没有$K_4$-!图子式的图的邻点可区别全色数. 证明了：如果 $G$是一个满足最大度$Delta ge 3$且没有$K_4$-!图子式的图, 则$Delta+1le chi''''_{a}(G)le Delta+2$, 且$chi''''_{a}(G)=Delta+2$当且仅当$G$中含有两个相邻最大度点.     

Pkn(k≡2(mod3))的D(2)-点可区别全染色

图的D(β)-点可区别全染色就是指图G的一个正常全染色且使得距离不大于β的任意两点有不同的色集合.讨论了幂图P_n~k当k≡2(mod3)时的D(2)-的点可区别全染色,并且根据P_n~2与C_n~2图的结构关系获得C_n~2的邻点可区别的全染色数.     

推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色

Mycielski图是在1955年由Mycielski首先提出的,推广的Mycielski图是在2003年由Peter Che Bor Lam,林文松等给出的Mycielski图的一个自然推广,且研究了它的圆色数.目前关于推广的Mycielski图性质以及它们在点色数,分数色数,圆色数等方面已有许多研究.本文定义了推广的Mycielski图的另一推广称为类推广的Mycielski图,且探讨了推广的Mycielski图和类推广的Mycielski图在全染色、邻点可区别全染色方面与原基础图的关系,从而也得到了它们满足全染色猜想和邻点可区别全染色猜想及它们达到全色数和邻点可区别的全色数的下界的一些充分条件.     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

轮与路的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射.如果(V)u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与路间的多重联图的邻点可区别E-全色数,其中C(u)={f(u)}∪ {f(uv)|uv∈E(G)}.     

轮与星的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数.     

图的邻点可区别Ⅵ-全色数和邻点可区别E-全色数

利用穷染、递推的方法讨论了路、圈、完全图、轮和扇的邻点可区别Ⅵ-全染色.并用概率方法研究了一般图的邻点可区别E-全染色,给出了图的邻点可区别E-全色数的一个上界.即δ≥7且△≥28,则有x_(at)~e(G)≤10△,其中δ是图G的最小度,△是图G的最大度.     

若干Mycielski's图的邻点可区别E-全染色

针对简单图G与Mycielski's图之间的关系,讨论了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全染色,给出了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全色数.     

关于K_(2n)-E(C_m)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为X'_(vd)(G).用k_(2n)-E(C_m)表示2n阶完全图删去其中一条m阶路的边后得到的图,得到了K_(14)-E(C_4),K_(16)-E(C_4),K_(18)-E(C_5),K_(20)-E(C_5)的点可区别边色数分别为14,16,18,20.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.     

Vertex-distinguishing IE-total Colorings of Cycles and Wheels

Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u）=C（v） for any two different vertices u and v of V （G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt（G）, and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.     

Concise proofs for adjacent vertex-distinguishing total colorings

Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χ_at(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χ_at(G) when G is a complete graph or a cycle.     

P_m∨C_n及C_m∨C_n的点可区别全染色

为了找到联图P_m∨C_n及C_m∨C_n的点可区别全染色利用其组合度用构造法得到了P_m∨C_n及C_m∨C_n的点可区别全染色方法并得到了其点可区别全色数(m≠n).