✦ LIBER ✦

Acyclic 4-edge colouring of non-regular subcubic graphs in linear time

✍ Scribed by Lukot’ka, Robert

Book ID: 122206113
Publisher: Elsevier Science
Year: 2014
Tongue: English
Weight: 362 KB
Volume: 170
Category: Article
ISSN: 0166-218X
DOI: 10.1016/j.dam.2014.01.022

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

4-edge-coloring graphs of maximum degree

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

✍ San Skulrattanakulchai 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 65 KB

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.