The equitable total coloring of a graph G is a total coloring such that the numbers of elements in any two colors differ by at most one.The smallest number of colors needed for an equitable total coloring is called th...The equitable total coloring of a graph G is a total coloring such that the numbers of elements in any two colors differ by at most one.The smallest number of colors needed for an equitable total coloring is called the equitable total chromatic number.This paper contributes to the equitable total coloring of Fibonacci graphs F_(∆,n).We determine the equitable total chromatic numbers of F_(∆,n) for∆=3,4,5 and propose a conjecture on that for∆>=6.展开更多
A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph...A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.展开更多
It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete...It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let rid（G） denote the number of vertices of degree d in G, and let X＇es（G） be the equitable vertex distinguishing edge index of G. We show that a tree T holds nl （T） ≤ X ＇s （T） ≤ n1 （T） ＋ 1 and X＇s（T） = X＇es（T） if T satisfies one of the following conditions （i） n2（T） ≤△（T） or （ii） there exists a constant c with respect to 0 〈 c 〈 1 such that n2（T） △ cn1（T） and ∑3 ≤d≤△（T）nd（T） ≤ （1 - c）n1（T） ＋ 1.展开更多
For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [...For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [ci - cj] ≤1 for any two colors i and j, then c is an equitable edge coloring of G. The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring. The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G. In this paper, we determine the equitable adjacent strong chromatic index of the joins of paths and cycles. Precisely, we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.展开更多
The minimum number of total independent partition sets of V ∪ E of graph G（V,E） is called the total chromatic number of G denoted by χt（G）. If the difference of the numbers of any two total independent partition...The minimum number of total independent partition sets of V ∪ E of graph G（V,E） is called the total chromatic number of G denoted by χt（G）. If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one＇, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χet（G）. In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order.展开更多
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.展开更多
The total chromatic number χt(G) of a graph G(V,E) is the minimum number of total independent partition sets of V E, satisfying that any two sets have no common element. If the difference of the numbers of any two to...The total chromatic number χt(G) of a graph G(V,E) is the minimum number of total independent partition sets of V E, satisfying that any two sets have no common element. If the difference of the numbers of any two total independent partition sets of V E is no more than one, then the minimum number of total independent partition sets of V E is called the equitable total chromatic number of G, denoted by χet(G). In this paper, we have obtained the equitable total chromatic number of Wm Kn, Fm Kn and Sm Kn whi...展开更多
The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k d...The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one.In this paper,we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-fc-colorable for every integer k≥(Δ+1)/2 provided that Δ≥9.818d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.展开更多
基金Supported by the National Natural Science Foundation of China(Grant No.62072292)the Natural Science Foundation of Shandong Province(Grant No.ZR2020KF010).
文摘The equitable total coloring of a graph G is a total coloring such that the numbers of elements in any two colors differ by at most one.The smallest number of colors needed for an equitable total coloring is called the equitable total chromatic number.This paper contributes to the equitable total coloring of Fibonacci graphs F_(∆,n).We determine the equitable total chromatic numbers of F_(∆,n) for∆=3,4,5 and propose a conjecture on that for∆>=6.
基金supported by the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010)the Fundamental Research Funds for the Central Universities(No.JB170706)+5 种基金the Specialized Research Fund for the Doctoral Program of Higher Education(No.20130203120021)the National Natural Science Foundation of China(No.11301410)the National Natural Science Foundation of China(No.11501316)the Shandong Provincial Natural Science Foundation,China(No.ZR2014AQ001)the China Postdoctoral Science Foundation(No.2015M570569)supported by the Natural Science Foundation of Xinjiang Province of China(No.2015211A003)
文摘A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree A at least 15, 13 or 12 has an equitable △-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.
基金supported by the National Natural Science Foundation of China (61163054),supported by the National Natural Science Foundation of China (61163037)
文摘It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let rid（G） denote the number of vertices of degree d in G, and let X＇es（G） be the equitable vertex distinguishing edge index of G. We show that a tree T holds nl （T） ≤ X ＇s （T） ≤ n1 （T） ＋ 1 and X＇s（T） = X＇es（T） if T satisfies one of the following conditions （i） n2（T） ≤△（T） or （ii） there exists a constant c with respect to 0 〈 c 〈 1 such that n2（T） △ cn1（T） and ∑3 ≤d≤△（T）nd（T） ≤ （1 - c）n1（T） ＋ 1.
基金Supported by the Fundamental Research Funds for the Central Universities(Grant Nos. 2011B019)the National Natural Science Foundation of China (Grant Nos. 10971144+2 种基金1110102011171026)the Natural Science Foundation of Beijing (Grant No. 1102015)
文摘For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [ci - cj] ≤1 for any two colors i and j, then c is an equitable edge coloring of G. The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring. The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G. In this paper, we determine the equitable adjacent strong chromatic index of the joins of paths and cycles. Precisely, we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.
基金Supported by the National Natural Science Foundation of China(No.10771091)
文摘The minimum number of total independent partition sets of V ∪ E of graph G（V,E） is called the total chromatic number of G denoted by χt（G）. If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one＇, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χet（G）. In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order.
基金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.
基金the National Natural Science Foundation of China (No.10771091)
文摘The total chromatic number χt(G) of a graph G(V,E) is the minimum number of total independent partition sets of V E, satisfying that any two sets have no common element. If the difference of the numbers of any two total independent partition sets of V E is no more than one, then the minimum number of total independent partition sets of V E is called the equitable total chromatic number of G, denoted by χet(G). In this paper, we have obtained the equitable total chromatic number of Wm Kn, Fm Kn and Sm Kn whi...
基金Supported by National Natural Science Foundation of China(Grant Nos.11871055,11701440)。
文摘The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one.In this paper,we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-fc-colorable for every integer k≥(Δ+1)/2 provided that Δ≥9.818d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.
