Distance-2 Edge Coloring is NP-Complete
<|reference_start|>Distance-2 Edge Coloring is NP-Complete: 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.<|reference_end|>
@article{erickson2005distance-2,
    title={Distance-2 Edge Coloring is NP-Complete},
    author={Jeff Erickson (1), Shripad Thite (1), David P. Bunde (1) ((1)
  Department of Computer Science, University of Illinois at Urbana-Champaign,
  Urbana, IL, USA)},
    journal={arXiv preprint arXiv:cs/0509100},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0509100},
    primaryClass={cs.DM cs.CC}
}