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!
Clarifications:
-
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.
Best Answer
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.