4-edge-coloring graphs of maximum degree 3 in linear time

DOI10.1016/S0020-0190(01)00221-6zbMath1013.68139OpenAlexW2046410178MaRDI QIDQ1603501

San Skulrattanakulchai

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00221-6

zbMATH Keywords

algorithmsedge-coloringNP-completenesscubic graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

COLORING ALGORITHMS ON SUBCUBIC GRAPHS, New linear-time algorithms for edge-coloring planar graphs, How important are branching decisions: fooling MIP solvers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Path-based depth-first search for strong and biconnected components
• Matching theory
• The NP-Completeness of Edge-Coloring
• Dividing a Graph into Triconnected Components
• A Proof of 4-Coloring the Edges of a Cubic Graph
• Depth-First Search and Linear Graph Algorithms
• 25 pretty graph colouring problems