Distance-2 Edge Coloring is NP-Complete

David P. Bunde (1) ((1) Department of Computer Science; IL; Jeff Erickson (1); Shripad Thite (1); University of Illinois at Urbana-Champaign; Urbana; USA)

arxiv: cs/0509100 · v1 · submitted 2005-09-30 · 💻 cs.DM · cs.CC

Distance-2 Edge Coloring is NP-Complete

Jeff Erickson (1) , Shripad Thite (1) , David P. Bunde (1) ((1) Department of Computer Science , University of Illinois at Urbana-Champaign , Urbana , IL , USA) This is my paper

classification 💻 cs.DM cs.CC

keywords coloringedgedistance-2np-completebipartitecolorsdegreedetermine

0 comments

read the original 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.

This paper has not been read by Pith yet.

Distance-2 Edge Coloring is NP-Complete

discussion (0)