4
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ The second condition is a condition on the edges, not a condition on the colorings. Is the graph's edges fixed or not? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 17, 2010 at 3:28
  • $\begingroup$ Qiaochu, yes, there is a fixed number of edges |E| (not the greatest notation). |E| > N, where N is the number of available colors. $\endgroup$
    – AfternoonCoffee
    Commented Dec 17, 2010 at 3:38
  • $\begingroup$ @AfternoonCoffee: but is the location of the edges fixed? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 17, 2010 at 3:49
  • $\begingroup$ 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. $\endgroup$
    – AfternoonCoffee
    Commented Dec 17, 2010 at 3:59
  • $\begingroup$ @AfternoonCoffee: then why is the second condition a condition on the edges, not a condition on their colorings? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 17, 2010 at 4:08

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – AfternoonCoffee
    Commented Dec 17, 2010 at 16:23
  • $\begingroup$ It's probably worth stating that condition (1) defines this as a special case of the edge coloring problem. $\endgroup$
    – AfternoonCoffee
    Commented Dec 17, 2010 at 16:25
  • $\begingroup$ "...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. $\endgroup$
    – AfternoonCoffee
    Commented Dec 17, 2010 at 16:26
  • $\begingroup$ 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. $\endgroup$
    – Dave Pritchard
    Commented Dec 17, 2010 at 16:43
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – AfternoonCoffee
    Commented Dec 18, 2010 at 9:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .