Premium
Acyclic Edge Coloring of Triangle‐Free Planar Graphs
Author(s) -
Basavaraju Manu,
Chandran L. Sunil
Publication year - 2012
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.20651
Subject(s) - combinatorics , mathematics , edge coloring , discrete mathematics , planar graph , list coloring , graph factorization , graph power , complete coloring , graph , line graph
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a ′( G ). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a ′( G ) ⩽ Δ + 2, where Δ = Δ( G ) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition | E ( H )| ⩽ 2| V ( H )|−1, we say that the graph G satisfies Property A . In this article, we prove that if G satisfies Property A , then a ′( G ) ⩽ Δ + 3. Triangle‐free planar graphs satisfy Property A . We infer that a ′( G ) ⩽ Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory