# What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring.

Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.

My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!

• Perhaps Mixed or Colour-bounded Hypergraph Colouring might be a start? For instance, dx.doi.org/10.1016/j.disc.2008.04.019 Apr 27 '13 at 23:53
• It seems your problem is in P, in two steps: (1) your problem is equivalent to finding a maximum-size subset of the edges such that every vertex has degree at most two, and (2) the latter problem seems to be in P by, say, reduction to matching. Regarding (1), note that any solution to your problem with k colors gives a degree-2 subgraph of size k (just retain one edge from each color), and conversely any degree-2 subgraph of size k gives a solution with k colors (just color each edge in the subgraph its own color, color the rest of the edges with any one of the colors). What am I missing? May 2 '13 at 4:10
• I am sorry that there are several mistakes in your answer. At first, the problem "finding a maximum-size subset of the edges such that every vertex has degree at most two", is NP-hard, reduction to 3SAT(I do not really know how could it have reduction to matching). What's more, "any degree-2 subgraph of size k" does not give "a solution with k colors", for example, Complete Graph. Thank you all the same. May 2 '13 at 6:33
• Yes, you're right. About (2), the step "color the rest of the edges with any one of the colors" can give some vertex edges of three colors. Separately, Marek Chrobak suggested the following algorithm to me. I think it gives a 3-approximation: (i) find a maximum matching M; (ii) color each edge in M its own unique color; (iii) color the remaining edges white. May 2 '13 at 15:10
• @RIC_Eien: At the risk of further embarrassment.. Are you sure "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is NP-hard"? Given G=(V,E), create bipartite G2=(U,W,E2), where for each vertex v in V there is v' in U and v'' in W, and E2={(u',w'') : (u,w) in E}. Then the matchings in G2 correspond to the degree-2 sets of edges in G, and the correspondence preserves size? (As each k-cycle C in G corresponds in G2 to either a 2k-cycle (if k odd) or two k-cycles (if k even).) So max-matching in G2 solves it. What am I missing this time? May 2 '13 at 15:25

This problem is NP-hard and APX-hard; see: Adamaszek and Popa, Approximation and Hardness Results for the Maximum Edge $q$-coloring Problem, Lecture Notes in Computer Science 6507 (2010) 132-143.