Return to Question

Please imagine the case where one has a 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.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size one.

Is there an efficient algorithm for coloring the edges of $G$ provided these constraints? Is there are known computational complexity for the problem? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

I appreciate everyone's time!

Clarification - 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. (thanks domotorp!)

EDIT 3 - We can further restrict $G$, the graph under consideration, to be a planar graph.

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

EDIT - 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.

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.

Please imagine the case where one has a 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.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size one.

Is there an efficient algorithm for coloring the edges of $G$ provided these constraints? Is there are known computational complexity for the problem? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

I appreciate everyone's time!

EDIT 3 - We can further restrict $G$, the graph under consideration, to be a planar graph.

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

EDIT - 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.

Please imagine the case where one has a 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.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size one.

Is there an efficient algorithm for coloring the edges of $G$ provided these constraints? Is there are known computational complexity for the problem? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

I appreciate everyone's time!

Clarification - 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. (thanks domotorp!)

EDIT 3 - We can further restrict $G$, the graph under consideration, to be a planar graph.

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

EDIT - 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.

Please imagine the case where one has a 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.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size one.

Is there an efficient algorithm for coloring the edges of $G$ provided these constraints? Is there are known computational complexity for the problem? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

I appreciate everyone's time!

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

EDIT - 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.

Please imagine the case where one has a 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.

(2) - The intersection, or overlap, between the colors of the edges of any two vertices is, at most, of size one.

Is there an efficient algorithm for coloring the edges of $G$ provided these constraints? Is there are known computational complexity for the problem? Does the problem become considerably simpler if one tightens the bounds on the size of vertex edge sets?

I appreciate everyone's time!

EDIT 3 - We can further restrict $G$, the graph under consideration, to be a planar graph.

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

EDIT - 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.