acyclic coloring of graphs by Frati

König’s line coloring theorem: every bicubic graph has a Tait coloring. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings.

two spaces are homeomorphic if one can be deformed into the other without cutting or gluing.

Vizing’s theorem: every cubic graph needs either three or four colors for an edge coloring

Brooks’ theorem: every cubic graph other than the complete graph K4 can be colored with at most three colors

Advertisements