Algorithmic aspects of acyclic edge colorings

DOI10.1007/S00453-001-0093-8MaRDI QIDQ1348909zbMATH OpenOpenAlexFDO

Authors Noga Alon, Ayal Zaks

Publication date 21 May 2002

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-001-0093-8

zbMATH Keywords

acyclic edge chromatic number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices
• Acyclic coloring of graphs of maximum degree
• Acyclic edge colourings of graphs with large girth
• Improved upper bounds on acyclic edge colorings
• Acyclic edge coloring of graphs with large girths

Cited in

(35)

• Acyclic edge colorings of planar graphs and series parallel graphs
• Acyclic edge coloring of planar graphs without small cycles
• Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices
• Acyclic chromatic index of planar graphs with triangles
• Efficient algorithms for acyclic colorings of graphs
• Acyclic chromatic indices of planar graphs with large girth
• The method of coloring in graphs and its application
• Acyclic edge-coloring using entropy compression
• Acyclic 4-edge colouring of non-regular subcubic graphs in linear time
• A survey of graph coloring -- its types, methods and applications
• An algorithm for optimal acyclic edge-colouring of cubic graphs
• Acyclic edge chromatic number of outerplanar graphs
• Planarization and acyclic colorings of subcubic claw-free graphs
• Acyclic edge coloring of 2-degenerate graphs
• Optimal Acyclic Edge Colouring of Grid Like Graphs
• Acyclic edge coloring of graphs with maximum degree 4
• Acyclic chromatic indices of planar graphs with girth at least five
• Acyclic chromatic indices of fully subdivided graphs
• On the adjacent vertex-distinguishing acyclic edge coloring of some graphs
• Acyclic edge coloring of triangle-free planar graphs
• Acyclic total colorings of planar graphs without \(l\) cycles
• Improved bounds for acyclic chromatic index of planar graphs
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• Acyclic, star, and injective colouring: bounding the diameter
• Acyclic chromatic index of chordless graphs
• Hardness transitions and uniqueness of acyclic colouring
• Improved bounds on linear coloring of plane graphs
• Acyclic, star and injective colouring: a complexity picture for H-free graphs
• Optimal acyclic edge colouring of grid like graphs
• Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs
• Computational results on semistrong edge coloring of graphs
• Acyclic colorings of subcubic graphs
• Analysis of a heuristic for acyclic edge colouring
• About acyclic edge colourings of planar graphs
• Acyclic edge coloring of subcubic graphs

This page was built for publication: Algorithmic aspects of acyclic edge colorings

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