A proper edge coloring of a graph is a coloring of its edges such that nowhere are two edges of the same color incident to a node. A proper edge coloring of a cubic graph using three colors is called a Tait coloring. (Note, that if a cubic graph has a Tait coloring, it may well have many.)
An example of a trivalent graph that does not have a Tait coloring is the Peterson graph.
 |
| Nearly all cubic graphs have a Tait coloring. The Petersen graph is an example of one that does not. |
Because each edge in a Tait-colored graph belongs to two cycles of alternating edge colors, no graph with a bridge can have a Tait coloring. (More obviously, no graph with a self-loop can have a Tait coloring, but all such cubic graphs have a bridge as well.)
Every bicubic (bipartite cubic) graph has a Tait coloring.
Every Hamiltonian cubic graph has a Tait coloring.
Since nearly all cubic graphs are Hamiltonian, it follows that nearly all are Tait-colorable.
Every bridge-free, planar cubic graph has a Tait coloring. (A consequence of the Four Color Theorem.)
A Heawood node 2-coloring is a node-2-coloring of a plane (i.e., embedded planar) graph under the condition that the number of black and white nodes in every face cycle are equal mod 3. A bridge-free planar, cubic graph can be Tait colored if and only if it can be Heawood node-2-colored; hence, as a consequence of the Four Color Theorem, every bridge-free, planar cubic graph can be Heawood node 2-colored.
No comments:
Post a Comment