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.展开更多
A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets. According to the property of trees, the adjacent vertex distinguishing total chromatic numbe...A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets. According to the property of trees, the adjacent vertex distinguishing total chromatic number will be determined for the Mycielski graphs of trees using the method of induction.展开更多
Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent ...Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent edges receive the same color. An Ⅰ-total coloring of a graph G is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, we have C_φ(u) = C_φ(v), where C_φ(u) denotes the set of colors of u and its incident edges. The minimum number of colors required for an adjacent vertex distinguishing Ⅰ-total coloring of G is called the adjacent vertex distinguishing Ⅰ-total chromatic number, denoted by χ_at^i(G).In this paper, we characterize the adjacent vertex distinguishing Ⅰ-total chromatic number of outerplanar graphs.展开更多
A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of ...A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv∈ E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by X＇Aa（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.展开更多
For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? 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) | ...For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? 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 ? T N (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 (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χ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 ? χast(G) ? Δ(G) + 2 for any tree or unique cycle graph G.展开更多
In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number...In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.展开更多
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△.展开更多
Let G be a simple graph. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. Let Cf(v) = {f(v)} ∪ {f(vw)|w ∈ V (G),vw ∈ E(G)} for every v ∈ V (G). If f is a k-proper- total-coloring, and for u,v ∈ V (G),uv ∈ E...Let G be a simple graph. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. Let Cf(v) = {f(v)} ∪ {f(vw)|w ∈ V (G),vw ∈ E(G)} for every v ∈ V (G). If f is a k-proper- total-coloring, and for u,v ∈ V (G),uv ∈ E(G), we have Cf(u) = Cf(v), then f is called a k- adjacent-vertex-distinguishing total coloring (k-AV DTC for short). Let χat(G) = min{k|G have a k-adjacent-vertex-distinguishing total coloring}. Then χat(G) is called the adjacent-vertex- distinguishing total chromatic number (AV DTC number for short)...展开更多
A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges ...A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.展开更多
A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of ...A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of uw, and the adjacent strong edge chromatic number is defined as x'as(G) = min{k| there is a k-adjacent strong edge coloring of G}. In this paper, it has been proved that △ ≤ x'as(G) ≤ △ + 1 for outer plane graphs with △(G) ≥ 5, and X'as(G) = △ + 1 if and only if there exist adjacent vertices with maximum degree.展开更多
基金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.
基金Foundation item： Supported by Natural Science Foundation of China（60503002）
文摘A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets. According to the property of trees, the adjacent vertex distinguishing total chromatic number will be determined for the Mycielski graphs of trees using the method of induction.
基金Supported by the National Natural Science Foundation of China(61163037,61163054,61363060)
文摘Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent edges receive the same color. An Ⅰ-total coloring of a graph G is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, we have C_φ(u) = C_φ(v), where C_φ(u) denotes the set of colors of u and its incident edges. The minimum number of colors required for an adjacent vertex distinguishing Ⅰ-total coloring of G is called the adjacent vertex distinguishing Ⅰ-total chromatic number, denoted by χ_at^i(G).In this paper, we characterize the adjacent vertex distinguishing Ⅰ-total chromatic number of outerplanar graphs.
基金supported by NSFC of China (No. 19871036 and No. 40301037)Faculty Research Grant,Hong Kong Baptist University
文摘A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv∈ E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by X＇Aa（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.
基金the National Natural Science Foundation of China (Grant Nos. 10771091, 10661007)
文摘For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? 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 ? T N (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 (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χ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 ? χast(G) ? Δ(G) + 2 for any tree or unique cycle graph G.
文摘In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.
基金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 National Natural Science Foundation of China (No.10771091)the Science and Research Project of the Education Department of Gansu Province (No.0501-02)
文摘Let G be a simple graph. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. Let Cf(v) = {f(v)} ∪ {f(vw)|w ∈ V (G),vw ∈ E(G)} for every v ∈ V (G). If f is a k-proper- total-coloring, and for u,v ∈ V (G),uv ∈ E(G), we have Cf(u) = Cf(v), then f is called a k- adjacent-vertex-distinguishing total coloring (k-AV DTC for short). Let χat(G) = min{k|G have a k-adjacent-vertex-distinguishing total coloring}. Then χat(G) is called the adjacent-vertex- distinguishing total chromatic number (AV DTC number for short)...
基金Supported by the Natural Science Foundation of Gansu Province(3ZS051-A25-025)
文摘A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.
基金National Natural Science Foundation of China (No. 19871036) Qinglan talent Funds of Lanzhou Jiaotong University.
文摘A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of uw, and the adjacent strong edge chromatic number is defined as x'as(G) = min{k| there is a k-adjacent strong edge coloring of G}. In this paper, it has been proved that △ ≤ x'as(G) ≤ △ + 1 for outer plane graphs with △(G) ≥ 5, and X'as(G) = △ + 1 if and only if there exist adjacent vertices with maximum degree.
基金Supported by Natural Science Poundation of China(60474029)Gansu Province Scientific Breakthroughs Project(2GS035-A052-011)Knowledge Innovation Project of Northwest Normal University(NWNU-KJCXGC-02-03)the Youth Teacher Foundation of Northwest Normal University(NWNU-QN-2003-22).
