An algorithm for optimal acyclic edge-colouring of cubic graphs

DOI10.1007/978-3-642-21204-8_17MaRDI QIDQ3004663zbMATH OpenOpenAlexFDO

Authors E. Máčajová, J. Mazák

Publication date 3 June 2011

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21204-8_17

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Optimal acyclic edge-coloring of cubic graphs
• Acyclic colorings of subcubic graphs
• Acyclic 4-edge colouring of non-regular subcubic graphs in linear time
• Acyclic edge coloring of subcubic graphs
• Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

Cites work

• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Acyclic colorings of subcubic graphs
• Acyclic edge coloring of subcubic graphs
• Acyclic edge colorings of graphs
• Algorithmic aspects of acyclic edge colorings
• scientific article; zbMATH DE number 3882456 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• Introduction to algorithms
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
• The acyclic edge chromatic number of a random d‐regular graph is d + 1

Cited in

(13)

• 4-edge-coloring graphs of maximum degree 3 in linear time
• Generalized arboricity of graphs with large girth
• Efficient algorithms for acyclic colorings of graphs
• Note on incidence chromatic number of subquartic graphs
• Acyclic 4-edge colouring of non-regular subcubic graphs in linear time
• Planarization and acyclic colorings of subcubic claw-free graphs
• Optimal Acyclic Edge Colouring of Grid Like Graphs
• Optimal acyclic edge-coloring of cubic graphs
• scientific article; zbMATH DE number 2089961 (Why is no real title available?)
• Optimal acyclic edge colouring of grid like graphs
• A cubic algorithm for the directed Eulerian subgraph problem
• Acyclic colorings of subcubic graphs
• Acyclic edge coloring of subcubic graphs

This page was built for publication: An algorithm for optimal acyclic edge-colouring of cubic graphs

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