Distance-2 Edge Coloring is NP-Complete

Simple item page
dc.creatorErickson, Jeff
dc.creatorThite, Shripad
dc.creatorBunde, David P.
dc.date2005-09-30
dc.date.accessioned2026-07-07T06:19:49Z
dc.date.available2026-07-07T06:19:49Z
dc.descriptionWe 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.
dc.description3 pages, 1 figure in color
dc.identifierhttps://arxiv.org/abs/cs/0509100
dc.identifierhttp://arxiv.org/abs/cs/0509100
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/95157
dc.subjectDiscrete Mathematics
dc.subjectComputational Complexity
dc.titleDistance-2 Edge Coloring is NP-Complete
dc.typetext

Files

Collections

arXiv