Acyclic edge coloring of sparse graphs

DOI10.1016/J.DISC.2012.08.012MaRDI QIDQ1759399zbMATH OpenOpenAlexFDO

Authors Ping Sheng, Yingqian Wang

Publication date 20 November 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2012.08.012

zbMATH Keywords

acyclic chromatic indexacyclic edge coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Acyclic edge coloring of planar graphs without 5-cycles
• On acyclic edge coloring of planar graphs without intersecting triangles
• Acyclic edge coloring of graphs with maximum degree 4
• Acyclic edge coloring of planar graphs without 4-cycles
• Acyclic edge colorings of graphs

Cites work

• About acyclic edge colourings of planar graphs
• Acyclic chromatic index of planar graphs with triangles
• Acyclic edge coloring of graphs with maximum degree 4
• Acyclic edge coloring of planar graphs without small cycles
• Acyclic edge coloring of triangle-free planar graphs
• Acyclic edge colorings of graphs
• Acyclic edge colorings of planar graphs and series parallel graphs
• Acyclic edge colouring of planar graphs without short cycles
• Acyclic edge-coloring of planar graphs
• Graph theory
• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• Improved bounds for acyclic chromatic index of planar graphs
• Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles
• On acyclic edge coloring of planar graphs without intersecting triangles
• Some results on acyclic edge coloring of plane graphs

Cited in

(19)

• A note on acyclic edge coloring of complete bipartite graphs
• Acyclic edge-colorings of sparse graphs
• Acyclic edge coloring of chordal graphs with bounded degree
• Acyclic edge coloring of 4-regular graphs. II.
• Acyclic edge coloring of graphs
• The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle
• Acyclic edge-coloring using entropy compression
• Acyclic edge colorings of graphs
• Acyclic edge coloring of triangle-free toroidal graphs.
• Strong edge coloring sparse graphs
• Optimal Acyclic Edge Colouring of Grid Like Graphs
• On acyclic edge coloring of planar graphs without intersecting triangles
• Acyclic edge coloring of triangle-free planar graphs
• Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle
• On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\)
• Acyclic chromatic indices of \(K_4\)-minor free graphs
• A GRASP for coloring sparse graphs
• Upper bounds on the acyclic chromatic index of degenerate graphs
• Optimal acyclic edge colouring of grid like graphs

This page was built for publication: Acyclic edge coloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759399)