patternMinor
Normal colorings of cubic graphs (part 1)
Viewed 0 times
cubicpartgraphsnormalcolorings
Problem
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
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.
...
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.
Solution
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.
This construction also gives an affirmative answer to Question 2.
Context
StackExchange Computer Science Q#111046, answer score: 2
Revisions (0)
No revisions yet.