A new upper bound on the acyclic chromatic indices of planar graphs |
| |
Authors: | Weifan Wang Qiaojun Shu Yiqiao Wang |
| |
Institution: | 1. Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China;2. School of Management, Beijing University of Chinese Medicine, Beijing 100029, China |
| |
Abstract: | An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. It was conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we prove that if G is a planar graph, then a′(G)≤Δ+7. This improves a result by Basavaraju et al. M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet, T. Müller, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math. 25 (2011) 463–478], which says that every planar graph G satisfies a′(G)≤Δ+12. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|