| Distance-2 edge coloring is NPcomplete (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Let G be a simple, undirected graph. We say that two edges of G are within distance 2 of each other if either they are adjacent or there is some other edge that is adjacent to both of them. A distance-2-edge-coloring of G is an assignment of colors to edges so that any two edges within distance 2 of each other have distinct colors, or equivalently, a vertex-coloring of the square of the line graph of G. If the coloring uses only k colors, it is called a k-D2-edge-coloring, and the graph G is said to be k-D2-edge-colorable. Any k-D2-edge-colorable graph is also (k + 1)-D2-edge-colorable. Theorem 1. Determining whether a bipartite graph with girth 6 and maximum degree 3 is 5-D2edge-colorable is NP-complete. Proof: The problem is clearly in NP since a coloring can be verified in polynomial time. To prove NP-hardness, we describe a reduction from Not-All-Equal-3SAT [1, Problem LO3]. Instance: A set X = {x1, x2,..., xn} of variables, and a collection C = {C1, C2,..., Cm} of boolean clauses over X, each with exactly three literals. Question: Is there a truth assignment for X such that each clause in C has at least one true literal and at least one false literal? Given an instance (X, C) of Not-All-Equal-3SAT, we will reduce it to a graph G(X, C) | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||