Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ...Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ≠ Cf（v） for uv ∈ V（G）,uv E E（G）, then f is called k-adjacentvertex-distinguishing total coloring of G（k-AVDTC of G for short）. Let χat（G） = min{k｜G has a k-adjacent-vertex-distinguishing total coloring}. Then χat（G） is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic number on the Cartesion product of path Pm and complete graph Kn is obtained.展开更多
Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maxim...Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.展开更多
Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distingu...Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.展开更多
Let f be a proper total k-coloring of a simple graph G. For any vertex x ∈ V（G）, let Cf（x） denote the set of colors assigned to vertex x and the edges incident with x. If Cf（u） ≠ Cf（v） for all distinct verti...Let f be a proper total k-coloring of a simple graph G. For any vertex x ∈ V（G）, let Cf（x） denote the set of colors assigned to vertex x and the edges incident with x. If Cf（u） ≠ Cf（v） for all distinct vertices u and v of V（G）, then f is called a vertex- distinguishing total k-coloring of G. The minimum number k for which there exists a vertex- distinguishing total k-coloring of G is called the vertex-distinguishing total chromatic number of G and denoted by Xvt（G）. The vertex-disjoint union of two cycles of length n is denoted by 2Cn. We will obtain Xvt（2Cn） in this paper.展开更多
A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong ed...A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.展开更多
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) ? 2 3 |V (G)|+ 23 6 , where d(G) denotes the degree of a vertex in G, then χT (G) ? d(G) + 2.展开更多
In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple set...In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.展开更多
For positive integers k and r,a(k,r)-coloring of graph G is a proper vertex k-coloring of G such that the neighbors of any vertex v∈V(G)receive at least min{d_(G)(v),r}different colors.The r-hued chromatic number of ...For positive integers k and r,a(k,r)-coloring of graph G is a proper vertex k-coloring of G such that the neighbors of any vertex v∈V(G)receive at least min{d_(G)(v),r}different colors.The r-hued chromatic number of G,denoted χ_(r)(G),is the smallest integer k such that G admits a(k,r)-coloring.Let Q_(n) be the n-dimensional hypercube.For any integers n and r with n≥2 and 2≤r≤5,we investigated the behavior of χ_(r)(Q_(n)),and determined the exact value of χ_(2)(Q_(n))and χ_(3)(Q_(n))for all positive integers n.展开更多
Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree...Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree of G. This paper proves the conjecture for the case △(G) ≤4.展开更多
基金the Science and Research Project of Education Department of Gansu Province (0501-02)
文摘Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ≠ Cf（v） for uv ∈ V（G）,uv E E（G）, then f is called k-adjacentvertex-distinguishing total coloring of G（k-AVDTC of G for short）. Let χat（G） = min{k｜G has a k-adjacent-vertex-distinguishing total coloring}. Then χat（G） is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic number on the Cartesion product of path Pm and complete graph Kn is obtained.
基金the National Natural Science Foundation the Doctoral Foundation of the Education Committee of China.
文摘Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.
基金supported by National Natural Science Foundation of China(Grant Nos.11101243 and 11371355)the Research Fund for the Doctoral Program of Higher Education of China(Grant No.20100131120017)the Scientific Research Foundation for the Excellent Middle Aged and Youth Scientists of Shandong Province of China(Grant No.BS2012SF016)
文摘Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.
文摘Let f be a proper total k-coloring of a simple graph G. For any vertex x ∈ V（G）, let Cf（x） denote the set of colors assigned to vertex x and the edges incident with x. If Cf（u） ≠ Cf（v） for all distinct vertices u and v of V（G）, then f is called a vertex- distinguishing total k-coloring of G. The minimum number k for which there exists a vertex- distinguishing total k-coloring of G is called the vertex-distinguishing total chromatic number of G and denoted by Xvt（G）. The vertex-disjoint union of two cycles of length n is denoted by 2Cn. We will obtain Xvt（2Cn） in this paper.
基金Supported by NNSFC(19871036)"Qing Lan"talent funds of Lanzhou Railway Institute.
文摘A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.
基金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) ? 2 3 |V (G)|+ 23 6 , where d(G) denotes the degree of a vertex in G, then χT (G) ? d(G) + 2.
基金Supported by the National Natural Science Foundation of China (11761064)。
文摘In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.
基金supported by Natural Science Foundation of Xinjiang Uygur Autonomous Region of China“Spanning connectivity and supereulerian properties of graphs”(2022D01C410).
文摘For positive integers k and r,a(k,r)-coloring of graph G is a proper vertex k-coloring of G such that the neighbors of any vertex v∈V(G)receive at least min{d_(G)(v),r}different colors.The r-hued chromatic number of G,denoted χ_(r)(G),is the smallest integer k such that G admits a(k,r)-coloring.Let Q_(n) be the n-dimensional hypercube.For any integers n and r with n≥2 and 2≤r≤5,we investigated the behavior of χ_(r)(Q_(n)),and determined the exact value of χ_(2)(Q_(n))and χ_(3)(Q_(n))for all positive integers n.
文摘Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree of G. This paper proves the conjecture for the case △(G) ≤4.
