A

**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**

*proper edge coloring***. (Note, that if a cubic graph has a Tait coloring, it may well have many.)**

*Tait coloring*
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

**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.***Heawood node 2-coloring*
## No comments:

Post a Comment