4-edge-coloring graphs of maximum degree 3 in linear time
Article Ecrit par: Skulrattanakulchai, San ;
Résumé: We present a linear time algorithm to properly color the edges of any graph of maximum degree 3 using 4 colors. Our algorithm uses a greedy approach and utilizes a new structure theorem for such graphs.
Langue:
Anglais
Thème
Informatique
Mots clés:
Algorithms
NP-completeness
Edge-coloring
Cubic graphs
