Distance-2 Edge Coloring is NP-Complete

2005/09/30 by Jeff Erickson, Erickson, Jeff, Shripad Thite +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0509100

3 pages, 1 figure in color

arxiv created 2005/09/30 · openalex publication_date 2005/09/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and maximum degree 3.

Cited by

• Strong Edge Coloring for Channel Assignment in Wireless Radio Networks

Related

• 2-distance (Δ+2)-coloring of sparse graphs
• Some results on 2-distance coloring of planar graphs with girth five
• An improved bound for 2-distance coloring of planar graphs with girth six
• 2-distance (Δ+1)-coloring of sparse graphs using the potential method
• On 2-Distance (Δ+4)-coloring of planar graphs with girth at least five