Acyclic edge coloring of planar graphs without 4‐cycles

Acyclic edge coloring of planar graphs without 4‐cycles

0.00 Avg rating0 Votes
Article ID: iaor20132797
Volume: 25
Issue: 4
Start Page Number: 562
End Page Number: 586
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: graph coloring
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. Fiamčik (1978) and later Alon, Sudakov and Zaks (2001) conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we confirm this conjecture for planar graphs G with Δ≠ 4 and without 4‐cycles.

Reviews

Required fields are marked *. Your email address will not be published.