A proper total-coloring of graph G is said to be?equitable if the number of elements (vertices and edges) in any?two color classes differ by at most one, which the required?minimum number of colors is called the equit...A proper total-coloring of graph G is said to be?equitable if the number of elements (vertices and edges) in any?two color classes differ by at most one, which the required?minimum number of colors is called the equitable total chromatic?number. In this paper, we prove some theorems on equitable?total coloring and derive the equitable total chromatic numbers?of Pm V?Sn, Pm V?Fn and Pm V Wn.展开更多
图 G 的全部的色彩的数字 T (G) 是需要渲染 G 的元素(顶点和边) 的颜色的最小的数字以便不邻近或元素的事件对收到一样的颜色。G 被称为类型 1 如果 T (G)=(G)+ 1。在这份报纸,我们证明完全的由两部组成的图 Km, n 和周期 Cn 的 join...图 G 的全部的色彩的数字 T (G) 是需要渲染 G 的元素(顶点和边) 的颜色的最小的数字以便不邻近或元素的事件对收到一样的颜色。G 被称为类型 1 如果 T (G)=(G)+ 1。在这份报纸,我们证明完全的由两部组成的图 Km, n 和周期 Cn 的 join 具有类型 1。展开更多
A planar graph G is called a i pseudo outerplanar graph if there is a subset V 0V(G),|V 0|=i, such that G-V 0 is an outerplanar graph. In particular, when G-V 0 is a forest, G is called a i...A planar graph G is called a i pseudo outerplanar graph if there is a subset V 0V(G),|V 0|=i, such that G-V 0 is an outerplanar graph. In particular, when G-V 0 is a forest, G is called a i pseudo tree. In this paper, the following results are proved: (i) The conjecture on the total coloring is true for all 1 pseudo outerplanar graphs; (ii) χ t(G)=Δ(G)+1 for any 1 pseudo outerplanar graph G with Δ(G)6 and for any 1 pseudo tree G with Δ(G)3, where χ t(G) is the total chromatic number of a graph G .展开更多
An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees.The purpose of this paper is to derive exact values of acyclic chromatic n...An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees.The purpose of this paper is to derive exact values of acyclic chromatic number of some graphs.展开更多
Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) + 1≤Xve(G)≤Δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not bee...Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) + 1≤Xve(G)≤Δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.展开更多
Let G = (V, E) be a simple connected graph, and |V(G)| ≥ 2. Let f be a mapping from V(G) ∪ E(G) to {1,2…, k}. If arbitary uv ∈ E(G),f(u) ≠ f(v),f(u) ≠ f(uv),f(v) ≠ f(uv); arbitary uv, uw...Let G = (V, E) be a simple connected graph, and |V(G)| ≥ 2. Let f be a mapping from V(G) ∪ E(G) to {1,2…, k}. If arbitary uv ∈ E(G),f(u) ≠ f(v),f(u) ≠ f(uv),f(v) ≠ f(uv); arbitary uv, uw ∈ E(G)(v ≠ w), f(uv) ≠ f(uw);arbitary uv ∈ E(G) and u ≠ v, C(u) ≠ C(v), whereC(u)={f(u)}∪{f(uv)|uv∈E(G)}.Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G(k-AVDTC of G for short). The number min{k|k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat(G). In this paper we prove that if △(G) is at least a particular constant and δ ≥32√△ln△, then χat(G) ≤ △(G) + 10^26 + 2√△ln△.展开更多
A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices' coloring sets are not identical and the difference of the elements colored by any...A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices' coloring sets are not identical and the difference of the elements colored by any two colors is not more than 1. In this paper we shall give vertex distinguishing equitable total chromatic number of join graphs Pn VPn, Cn VCn and prove that they satisfy conjecture 3, namely, the chromatic numbers of vertex distinguishing total and vertex distinguishing equitable total are the same for join graphs Pn V Pn and Cn ∨ Cn.展开更多
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 regula...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.展开更多
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....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 VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n (7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K7,n (7 ≤ n ≤ 95) has been obtained.展开更多
The total chromatic number XT(G) of graph G is the least number of colorsassigned to VE(G) such that no adjacent or incident elements receive the same color.Gived graphs G1,G2, the join of G1 and G2, denoted by G1∨G2...The total chromatic number XT(G) of graph G is the least number of colorsassigned to VE(G) such that no adjacent or incident elements receive the same color.Gived graphs G1,G2, the join of G1 and G2, denoted by G1∨G2, is a graph G, V(G) =V(GI)∪V(G2) and E(G) = E(G1)∪E(G2) ∪{uv | u∈(G1), v ∈ V(G2)}. In this paper, it's proved that if v(G) = v(H), both Gc and Hc contain perfect matching and one of the followings holds: (i)Δ(G) =Δ(H) and there exist edge e∈ E(G), e' E E(H)such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.展开更多
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 endpoi...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.展开更多
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 i...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.展开更多
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), i...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.展开更多
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of verte...Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x 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 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 χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.展开更多
文摘A proper total-coloring of graph G is said to be?equitable if the number of elements (vertices and edges) in any?two color classes differ by at most one, which the required?minimum number of colors is called the equitable total chromatic?number. In this paper, we prove some theorems on equitable?total coloring and derive the equitable total chromatic numbers?of Pm V?Sn, Pm V?Fn and Pm V Wn.
文摘A planar graph G is called a i pseudo outerplanar graph if there is a subset V 0V(G),|V 0|=i, such that G-V 0 is an outerplanar graph. In particular, when G-V 0 is a forest, G is called a i pseudo tree. In this paper, the following results are proved: (i) The conjecture on the total coloring is true for all 1 pseudo outerplanar graphs; (ii) χ t(G)=Δ(G)+1 for any 1 pseudo outerplanar graph G with Δ(G)6 and for any 1 pseudo tree G with Δ(G)3, where χ t(G) is the total chromatic number of a graph G .
文摘An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees.The purpose of this paper is to derive exact values of acyclic chromatic number of some graphs.
基金This work was partially supported by the National Natural Science Foundation of China (Grant No. 10471131)
文摘Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) + 1≤Xve(G)≤Δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.
基金the Natural Science Foundation of Gansu Province (No. 3ZS051-A25-025) the Foundation of Gansu Provincial Department of Education (No. 0501-03).
文摘Let G = (V, E) be a simple connected graph, and |V(G)| ≥ 2. Let f be a mapping from V(G) ∪ E(G) to {1,2…, k}. If arbitary uv ∈ E(G),f(u) ≠ f(v),f(u) ≠ f(uv),f(v) ≠ f(uv); arbitary uv, uw ∈ E(G)(v ≠ w), f(uv) ≠ f(uw);arbitary uv ∈ E(G) and u ≠ v, C(u) ≠ C(v), whereC(u)={f(u)}∪{f(uv)|uv∈E(G)}.Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G(k-AVDTC of G for short). The number min{k|k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat(G). In this paper we prove that if △(G) is at least a particular constant and δ ≥32√△ln△, then χat(G) ≤ △(G) + 10^26 + 2√△ln△.
基金the Xianyang Normal University Foundation for Basic Research(No.06XSYK266)Com~2 MaCKOSEP(R11-1999-054)
文摘A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices' coloring sets are not identical and the difference of the elements colored by any two colors is not more than 1. In this paper we shall give vertex distinguishing equitable total chromatic number of join graphs Pn VPn, Cn VCn and prove that they satisfy conjecture 3, namely, the chromatic numbers of vertex distinguishing total and vertex distinguishing equitable total are the same for join graphs Pn V Pn and Cn ∨ Cn.
基金supported by the Natural Science Foundation of Chongqing Science and Technology Commission(Grant No. 2007BB2123)
文摘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.
文摘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 VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n (7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K7,n (7 ≤ n ≤ 95) has been obtained.
文摘The total chromatic number XT(G) of graph G is the least number of colorsassigned to VE(G) such that no adjacent or incident elements receive the same color.Gived graphs G1,G2, the join of G1 and G2, denoted by G1∨G2, is a graph G, V(G) =V(GI)∪V(G2) and E(G) = E(G1)∪E(G2) ∪{uv | u∈(G1), v ∈ V(G2)}. In this paper, it's proved that if v(G) = v(H), both Gc and Hc contain perfect matching and one of the followings holds: (i)Δ(G) =Δ(H) and there exist edge e∈ E(G), e' E E(H)such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.
基金Supported by the NNSF of China(61163037,61163054)Supported by the Scientific Research Foundation of Ningxia University((E):ndzr09-15)
文摘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.
基金The NSF(61163037,61163054) of Chinathe Scientific Research Project(nwnu-kjcxgc-03-61) of Northwest Normal University
文摘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.
基金Supported by the NNSF of China(10771091)Supported by the Qinglan Project of Lianyungang Teacher’s College(2009QLD3)
文摘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.
基金Supported by the National Natural Science Foundation of China(61163037, 61163054, 11261046, 61363060)
文摘Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x 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 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 χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.