Editing Petersen graph (section)

== Coloring ==
[[Image:PetersenBarveniHran.svg|class=skin-invert-image|thumb|left|A 4-coloring of the Petersen graph's edges]]
[[Image:Petersen graph 3-coloring.svg|class=skin-invert-image|thumb|right|A 3-coloring of the Petersen graph's vertices]]

The Petersen graph has [[chromatic number]] 3, meaning that its vertices can be [[graph coloring|colored]] with three colors — but not with two — such that no edge connects vertices of the same color. It has a [[list coloring]] with 3 colors, by Brooks' theorem for list colorings.

The Petersen graph has [[chromatic index]] 4; coloring the edges requires four colors. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a [[snark (graph theory)|snark]]. It is the smallest possible snark, and was the only known snark from 1898 until 1946. The [[Snark (graph theory)|snark theorem]], a result conjectured by [[W. T. Tutte]] and announced in 2001 by Robertson, Sanders, Seymour, and Thomas,<ref>{{citation|last=Pegg|first=Ed Jr.|author-link=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=https://www.ams.org/notices/200209/rev-pegg.pdf | doi = 10.1109/TED.2002.1003756| bibcode= 2002ITED...49.1084A}}</ref> states that every snark has the Petersen graph as a [[Minor (graph theory)|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|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.

The Petersen graph requires at least three colors in any (possibly improper) coloring that breaks all of its symmetries; that is, its [[distinguishing number]] is three. Except for the complete graphs, it is the only Kneser graph whose distinguishing number is not two.<ref>{{citation
 | last1 = Albertson | first1 = Michael O.
 | last2 = Boutin | first2 = Debra L. | author2-link = Debra Boutin
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2285824
 | page = R20
 | title = Using determining sets to distinguish Kneser graphs
 | volume = 14
 | year = 2007| doi = 10.37236/938
 | doi-access = free
 }}.</ref>