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.展开更多
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 f be a proper edge coloring of G using k colors. For each x ∈ V（G）, the set of the colors appearing on the edges incident with x is denoted by Sf（x） or simply S（x） if no confusion arise. If S（u） = S（v） ...Let f be a proper edge coloring of G using k colors. For each x ∈ V（G）, the set of the colors appearing on the edges incident with x is denoted by Sf（x） or simply S（x） if no confusion arise. If S（u） = S（v） and S（v） S（u） for any two adjacent vertices u and v, then f is called a Smarandachely adjacent vertex distinguishing proper edge col- oring using k colors, or k-SA-edge coloring. The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number, or SA- edge chromatic number for short, and denoted by Xsa（G）. In this paper, we have discussed the SA-edge chromatic number of K4 V Kn.展开更多
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 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.展开更多
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.展开更多
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△.展开更多
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△.展开更多
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.展开更多
Let G（V, E） be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if （1） C（u）≠C（v） for uv ∈ E（G）, where C（u） = {f（uv）｜uv ∈ E}, a...Let G（V, E） be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if （1） C（u）≠C（v） for uv ∈ E（G）, where C（u） = {f（uv）｜uv ∈ E}, and （2） for any i, j = 1, 2,… k, we have ｜｜Ei｜ ｜Ej｜｜ ≤ 1, where Ei = {e｜e ∈ E（G） and f（e） = i}. χáve （G） = min{k｜ there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χ áve （G） of some special graphs and present a conjecture.展开更多
An adjacent vertex distinguishing incidence coloring of graph G is an incidence coloring of G such that no pair of adjacent vertices meets the same set of colors.We obtain the adjacent vertex distinguishing incidence ...An adjacent vertex distinguishing incidence coloring of graph G is an incidence coloring of G such that no pair of adjacent vertices meets the same set of colors.We obtain the adjacent vertex distinguishing incidence chromatic number of the Cartesian product of a path and a path,a path and a wheel,a path and a fan,and a path and a star.展开更多
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)...展开更多
基金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.
基金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 NNSF of China(61163037,61163054,61363060)
文摘Let f be a proper edge coloring of G using k colors. For each x ∈ V（G）, the set of the colors appearing on the edges incident with x is denoted by Sf（x） or simply S（x） if no confusion arise. If S（u） = S（v） and S（v） S（u） for any two adjacent vertices u and v, then f is called a Smarandachely adjacent vertex distinguishing proper edge col- oring using k colors, or k-SA-edge coloring. The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number, or SA- edge chromatic number for short, and denoted by Xsa（G）. In this paper, we have discussed the SA-edge chromatic number of K4 V Kn.
基金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.
基金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.
文摘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.
基金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△.
基金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 (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.
基金Supported by the National Natural Science Foundation of China(No.10771091No.61163010)Ningxia University Science Research Foundation(No.(E)ndzr09-15)
文摘Let G（V, E） be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if （1） C（u）≠C（v） for uv ∈ E（G）, where C（u） = {f（uv）｜uv ∈ E}, and （2） for any i, j = 1, 2,… k, we have ｜｜Ei｜ ｜Ej｜｜ ≤ 1, where Ei = {e｜e ∈ E（G） and f（e） = i}. χáve （G） = min{k｜ there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χ áve （G） of some special graphs and present a conjecture.
基金Supported by the State Ethnic Affairs Commission of China (Grant No. 08XB07)
文摘An adjacent vertex distinguishing incidence coloring of graph G is an incidence coloring of G such that no pair of adjacent vertices meets the same set of colors.We obtain the adjacent vertex distinguishing incidence chromatic number of the Cartesian product of a path and a path,a path and a wheel,a path and a fan,and a path and a star.
基金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 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).
