Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is th...Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is the Total Coloring Conjecture,which asserts that every graph of maximum degreeΔadmits a(Δ+2)-total-coloring.More precisely,this conjecture has been verified forΔ≤5,and it is still open whenΔ=6,even for planar graphs.Let mad(G)denote the maximum average degree of the graph G.In this paper,we prove that every graph G withΔ(G)=6 and mad(G)<23/5 admits an 8-total-coloring.展开更多
Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainb...Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.展开更多
A total-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v,the set of colors used on u and its incident edges and the set of colors used on v and its incident edges are no...A total-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v,the set of colors used on u and its incident edges and the set of colors used on v and its incident edges are not included with each other.The strict neighbor-distinguishing total indexχ"_(snd)(G)of G is the minimum number of colors in a strict neighbor-distinguishing total-coloring of G.In this paper,we prove that every simple graph G withΔ(G)≥3 satisfiesχ"_(snd)(G)≤2Δ(G).展开更多
基金This work was supported by the National Natural Science Foundation of China(11471193,11631014)the Foundation for Distinguished Young Scholars of Shandong Province(JQ201501)the Fundamental Research Funds of Shandong University and Independent Innovation Foundation of Shandong University(IFYT14012).
文摘Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is the Total Coloring Conjecture,which asserts that every graph of maximum degreeΔadmits a(Δ+2)-total-coloring.More precisely,this conjecture has been verified forΔ≤5,and it is still open whenΔ=6,even for planar graphs.Let mad(G)denote the maximum average degree of the graph G.In this paper,we prove that every graph G withΔ(G)=6 and mad(G)<23/5 admits an 8-total-coloring.
文摘Abstract A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc（G）, is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that trc（G） = 3 if （n-12） ＋ 1 ≤ ｜E（G）｜≤ （n2） - 1, and trc（G） ≤ 6 if ｜E（G）｜≥ （n22） ＋2. Next, we investigate the total rainbow connection numbers of graphs G with ｜V（G）｜ = n, diam（G） ≥ 2, and clique number w（G） = n - s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31（2）： 313-320] is not completely correct, and we provide a complete result for this theorem.
基金NSFC(Grant Nos.11771402,12031018,12071048)Science and Technology Commission of Shanghai Municipality(Grant No.18dz2271000)。
文摘A total-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v,the set of colors used on u and its incident edges and the set of colors used on v and its incident edges are not included with each other.The strict neighbor-distinguishing total indexχ"_(snd)(G)of G is the minimum number of colors in a strict neighbor-distinguishing total-coloring of G.In this paper,we prove that every simple graph G withΔ(G)≥3 satisfiesχ"_(snd)(G)≤2Δ(G).
