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.展开更多
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring u...An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.展开更多
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X'a(G), is the least number of colors such that G has an acyclic edge coloring. A gra...A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X'a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that X'a(G) ≤△ A(G)+ 22, if G is a triangle-free 1-planar graph.展开更多
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-p...A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex.In this paper,it is proved thatχ′a(G)≤Δ(G)+10,if G is an IC-planar graph without adjacent triangles andχ′a(G)≤Δ(G)+8,if G is a triangle-free IC-planar graph.展开更多
An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum numbe...An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a'(G) ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a'(G) 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a'(G) to 9.8△ and 9△ with girth 5 and 7, respectively.展开更多
A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic ...A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.展开更多
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△.展开更多
基金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.
基金Research supported by the National Natural Science Foundation of China (No.12031018)Research supported by the National Natural Science Foundation of China (No.12071048)+3 种基金Research supported by the National Natural Science Foundation of China(No.12071351)Science and Technology Commission of Shanghai Municipality (No.18dz2271000)Doctoral Scientific Research Foundation of Weifang University (No.2021BS01)Natural Science Foundation of Shandong Province (No.ZR2022MA060)。
文摘An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.
基金Supported by National Natural Science Foundation of China(Grant No.11271365)
文摘A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X'a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that X'a(G) ≤△ A(G)+ 22, if G is a triangle-free 1-planar graph.
基金supported by the National Natural Science Foundation of China (No. 11771443)Natural Science Foundation of Shandong Province (No. ZR2019BA016)+1 种基金by the foundation of innovative Science and technology for youth in universities of Shandong Province (No. 2019KJI001)under the financial support from the Zaozhaung University Research Fund Project in 2019
文摘A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex.In this paper,it is proved thatχ′a(G)≤Δ(G)+10,if G is an IC-planar graph without adjacent triangles andχ′a(G)≤Δ(G)+8,if G is a triangle-free IC-planar graph.
基金Supported by the National Natural Science Foundation of China(No.11371355)
文摘An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a'(G) ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a'(G) 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a'(G) to 9.8△ and 9△ with girth 5 and 7, respectively.
文摘A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.
基金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△.