4
$\begingroup$

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

  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.

Improve this question
$\endgroup$
7
  • $\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$
    – David Richerby
    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

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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