Take the 2-minute tour ×

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ colors, where $N < |E|$ (the number of edges), we seek to assign these colors to the edges of the graph such that:

(1) - The set of edges connected to any vertex contains edges with all unique colors, i.e. no two edges share the same color when attached to the same vertex. This condition should establish my question as a special case of the general case NP-Hard edge-coloring problem.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size $k = 1$ or $k = 2$. This condition must hold true regardless of whether the vertices are adjacent or not. (thanks domotorp!)

What would be the most efficient algorithm for coloring the edges of $G$ provided these constraints? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

My approach to the problem thus far has been to assign unique colors to all $|E|$ edges of a graph, i.e. to have $N = |E|$, and then proceed to reduce $N$ using a naive stochastic procedure. It would be great to have an efficient deterministic or semi-deterministic algorithm.

I appreciate everyone's time!


  • I am allowing the case of $k = 2$ as well as $k = 1$.

  • I changed criterion (2) from requiring that the intersection is of size 'k' to explicitly setting $k = 1$ (or $k = 2$), which is the case I am primarily interested in and hopefully better focuses this question.

share|improve this question
The second condition is a condition on the edges, not a condition on the colorings. Is the graph's edges fixed or not? –  Qiaochu Yuan Dec 17 '10 at 3:28
Qiaochu, yes, there is a fixed number of edges |E| (not the greatest notation). |E| > N, where N is the number of available colors. –  AfternoonCoffee Dec 17 '10 at 3:38
@AfternoonCoffee: but is the location of the edges fixed? –  Qiaochu Yuan Dec 17 '10 at 3:49
Yes, one is provided a fixed graph 'G'. Edges may be colored in any manner (so long as they obey the aforementioned constraints), but they cannot be rearranged. –  AfternoonCoffee Dec 17 '10 at 3:59
@AfternoonCoffee: then why is the second condition a condition on the edges, not a condition on their colorings? –  Qiaochu Yuan Dec 17 '10 at 4:08

2 Answers 2

I edited my answer after the clarification of the question.

Consider the union of two different color classes. This subgraph consists of disjoint edges and (possibly) a path of length 2. This gives the following bound if the paths can have length 2:

$\sum_i {deg(v_i) \choose 2}\le {N\choose 2}$

Of course this is just a necessary and not a sufficient condition, but it might be a good start for an NP-completeness proof.

share|improve this answer
Dear domotorp, condition (2) must hold true regardless of whether the vertices are adjacent or not. Therefore the answer to: "...if there are two adjacent vertices, then can they have another common color apart from the color of their common edge or no?" is no. I hope that simplifies matters, and an NP-completeness result for this problem would be fantastic. –  AfternoonCoffee Dec 18 '10 at 9:38

If the input number $k$ is very large (say as large as the next-to-maximum degree) then condition (2) has no effect, and this becomes the same as $N$-edge-colouring of a graph, which is NP-complete. (Have you read about this problem? It's NP-complete even for 3-regular graphs and $N=3$.) So if I understand correctly it does not seem that there is any hope of exactly solving this problem with an efficient algorithm. There are lots of results about finding an edge-colouring with approximately the minimum number of colours, classical ones include Vizing's theorem.

My brain can't parse the phrase "...bounds on the size of vertex edge sets..." but maybe in the last question you mean, is the problem easy if $k$ is small enough? In the case of 3-regular graphs with $N=3$, it makes it easier but for a trivial reason: no colouring meeting (1) and (2) is possible for any such graph if $k<3$, since any colouring meeting (1) would have to have all 3 colours appearing adjacent to every vertex.

share|improve this answer
Dear Dave, I'm setting k = 1 to better focus the question on the case I'm particularly interested in where k << N. I'm hoping I can differentiate this problem from the known NP-hard problem of N-edge coloring... –  AfternoonCoffee Dec 17 '10 at 16:23
It's probably worth stating that condition (1) defines this as a special case of the edge coloring problem. –  AfternoonCoffee Dec 17 '10 at 16:25
"...bounds on the size of vertex edge sets..." - sorry, by this I mean providing tight lower and upper-bounds for connectivity of each vertex in the graph. –  AfternoonCoffee Dec 17 '10 at 16:26
Ok, thanks! BTW the term is typically called "the degree of a vertex," connectivity already has a different standard meaning. It doesn't seem obvious to me whether or not this problem is NP-hard when $k=1$, so it is a good and interesting clarification. –  Dave Pritchard Dec 17 '10 at 16:43

Your Answer


