Mathematics (Aug 2022)

Acyclic Chromatic Index of 1-Planar Graphs

  • Wanshun Yang,
  • Yiqiao Wang,
  • Weifan Wang,
  • Juan Liu,
  • Stephen Finbow,
  • Ping Wang

DOI
https://doi.org/10.3390/math10152787
Journal volume & issue
Vol. 10, no. 15
p. 2787

Abstract

Read online

The acyclic chromatic index χa′(G) of a graph G is the smallest k for which G is a proper edge colorable using k colors. A 1-planar graph is a graph that can be drawn in plane such that every edge is crossed by at most one other edge. In this paper, we prove that every 1-planar graph G has χa′(G)≤Δ+36, where Δ denotes the maximum degree of G. This strengthens a result that if G is a triangle-free 1-planar graph, then χa′(G)≤Δ+16.

Keywords