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


  1. 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:

  1. Could you suggest an algorithm to find normal 5-colorings of cubic graphs if they exist?

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

  • $\begingroup$ Right, I am assuming that algorithms are known. I would not expect somebody to write the research paper for me ... but I may be wrong and nothing is known. As I said, it is my understanding something is known, I just don’t know about it. $\endgroup$
    – EGME
    Jun 22, 2019 at 10:22
  • $\begingroup$ OK, then that seems reasonable. $\endgroup$ Jun 22, 2019 at 10:24
  • $\begingroup$ Where is the conjecture coming from? Is there some evidence that it might be true? $\endgroup$
    – Juho
    Jun 27, 2019 at 5:22
  • $\begingroup$ @Juho The conjecture is Jaeger’s, it is well known (80’s??). It seems it might be true. It has sweeping implications in graph theory, and it has been “rediscovered” recently. In order to really get evidence, it would be nice to have a program to test on the large collection of cubic graphs available in The House of Graphs (see my post in MahtOverflow “Normal colorings of bridgeless cubic graphs”). $\endgroup$
    – EGME
    Jun 27, 2019 at 7:59
  • $\begingroup$ @Juho See also “Normal colorings of cubic graphs to SAT” on this site ... $\endgroup$
    – EGME
    Jun 27, 2019 at 8:48

1 Answer 1


Some old results by Vladimir Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165-176, imply that Question 3 has an affirmative answer. Although the auxiliary graph is not assured to be in some way as elegant or natural as in the case of line graphs or their squares. The easiest example that I can come up with has 13 times the order of the line graph. This construction also gives an affirmative answer to Question 2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.