Acyclic edge coloring of sparse graphs
type: Item
instance of: scholarly article
title: Acyclic edge coloring of sparse graphs
zbMATH Open document ID: 1270.05049
author: Ping Sheng
author: Yingqian Wang
published in: Discrete Mathematics
publication date: 2012-11-20T00:00:00Z
review text: An acyclic edge coloring of a graph \(G\) is a proper edge coloring that results in no bichromatic cycle. A graph \(G\) ist called acyclically edge \(k\)-colorable if it admits an acyclic edge coloring using at most \(k\) colours. The acyclic chromatic index of a graph \(G\) is the minimum number \(k\) such that \(G\) is acyclically edge \(k\)-colorable. In 1978 it was conjectured that every graph is acyclically edge \((\Delta+2)\)-colorable. In the present paper the conjecture is proved for graphs with maximum average degree less than 4. As a corollary, triangle-free planar graphs prove to be edge \((\Delta+2)\)-colorable.
reviewed by: Ulrike Baumann
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6108949
zbMATH Keywords: acyclic edge coloring
zbMATH Keywords: acyclic chromatic index
MaRDI profile type: Publication
full work available at URL: j.disc.2012.08.012
OpenAlex ID: W1978597841
cites work: Acyclic edge colorings of graphs
cites work: Acyclic edge coloring of graphs with maximum degree 4
cites work: Acyclic Edge Coloring of Triangle‐Free Planar Graphs
cites work: Acyclic Edge-Coloring of Planar Graphs
cites work: Q5422499
cites work: Acyclic edge colouring of planar graphs without short cycles
cites work: Some results on acyclic edge coloring of plane graphs
cites work: Q4168628
cites work: About acyclic edge colourings of planar graphs
cites work: Improved bounds for acyclic chromatic index of planar graphs
cites work: Acyclic edge coloring of planar graphs without small cycles
cites work: Acyclic chromatic index of planar graphs with triangles
cites work: Acyclic edge colorings of planar graphs and series parallel graphs
cites work: On acyclic edge coloring of planar graphs without intersecting triangles
cites work: Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles
DOI: 10.1016/J.DISC.2012.08.012
description: scientific article; zbMATH DE number 6108949