Coloring
The Petersen graph has chromatic number 3, meaning that its vertices can be colored with three colors — but not with two — such that no edge connects vertices of the same color.
The Petersen graph has chromatic index 4; coloring the edges requires four colors. A proof of this requires checking four cases to demonstrate that no 3-edge-coloring exists. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a snark. It is the smallest possible snark, and was the only known snark from 1898 until 1946. The snark theorem, a result conjectured by W. T. Tutte and announced in 2001 by Robertson, Sanders, Seymour, and Thomas, states that every snark has the Petersen graph as a minor.
Additionally, the graph has fractional chromatic index 3, proving that the difference between the chromatic index and fractional chromatic index can be as large as 1. The long-standing Goldberg-Seymour Conjecture proposes that this is the largest gap possible.
The Thue number (a variant of the chromatic index) of the Petersen graph is 5.
Read more about this topic: Petersen Graph