Edit 2019 June 27 Question 3 is new
...
Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or with three.
There is also the following
Conjecture Every bridgeless cubic graph (that is, a cubic graph without a cut edge) can be normally 5-colored.
We are looking for algorithms to normally color cubic graphs
Questions
- Could you suggest an algorithm to find normal $k$-colorings of cubic graphs, with $k$ at most 9, that is efficient and simple. The coloring should include at least one edge $e$ such that the $e$ and its adjacent edges are colored with 3 colors, if this is possible. It is known that 9 colors should suffice. It is my understanding that a linear time algorithm is known, but I've not been able to find it in the literature.
More importantly:
Could you suggest an algorithm to find normal 5-colorings of cubic graphs if they exist?
Can you find a way to color the graph using a vertex coloring algorithm ... to illustrate what I mean, to do edge coloring of a graph $G$, you perform vertex coloring on the line graph of $G$. To do strong edge coloring of $G$, you perform vertex coloring on the square graph of the line graph of $G$. In that same spirit, is there a reasonable auxiliary graph on which to do standard vertex coloring to achieve a normal coloring of $G$?
If there is a better site where this question could be posted, please indicate this. If this site is not for questions requesting information about algorithms, please notify and it will be removed immediately. I have never posted in this site.