Premium
Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4
Author(s) -
Shu Qiaojun,
Wang Weifan,
Wang Yiqiao
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21683
Subject(s) - combinatorics , edge coloring , mathematics , girth (graph theory) , planar graph , discrete mathematics , conjecture , graph , brooks' theorem , integer (computer science) , 1 planar graph , chordal graph , graph power , line graph , computer science , programming language
Abstract An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic indexa ′ ( G )of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiam c ̌ ik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured thata ′ ( G ) ≤ Δ + 2 for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.