Coloring and Independent Sets
According to Brooks' theorem every cubic graph other than the complete graph K4 can be colored with at most three colors. Therefore, every cubic graph other than K4 has an independent set of at least n/3 vertices, where n is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.
According to Vizing's theorem every cubic graph needs either three or four colors for an edge 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. By König's line coloring theorem every bicubic graph has a Tait coloring.
The bridgeless cubic graphs that do not have a Tait coloring are known as snarks. They include the Petersen graph, Tietze's graph, the Blanuša snarks, the flower snark, the double-star snark, the Szekeres snark and the Watkins snark. There is an infinite number of distinct snarks.
Read more about this topic: Cubic Graph
Famous quotes containing the words independent and/or sets:
“The soul of me is very selfish. I have gone my way after a fashion that made me the center of the plan. And you who are so individual, who are so independent a spirit, whose soul is also a kingdom, have been so loyal, so forgiving, so self-sacrificing in your willingness to live my life. Nothing but love cold have accomplished so wonderful a thing.”
—Woodrow Wilson (1856–1924)
“It provokes the desire but it takes away the performance. Therefore much drink may be said to be an equivocator with lechery: it makes him and it mars him; it sets him on and it takes him off.”
—William Shakespeare (1564–1616)