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.展开更多
基金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.
