Chromatic number of complement of Petersen graph

This is Petersen Graph -

It is an undirected graph, it is $3$-regular and it's chromatic number is $3$. Proof: There is a circle with $5$ nodes (the outside pentagon), a graph with a graph that contains a circle with an odd number of nodes is at least $3$. In the picture I gave a coloring with $3$ colors, so it is at most $3$ as well. The result is that the chromatic number is $3$.

The question is: What is the chromatic number of the complement of petersen graph? We can deduce that it will be $6$-regular, and the pentagram on the inside of petersen graph will be a pentagon in the complement, so the complement has chromatic number of at least $3$. I don't know where to go from here without actually color the graph and hope that I can do it with $3$ colors.

Important Edit: I found a clique of $4$ nodes in the complement, so the chromatic number is at least $4$.

• The complement is 5-colorable: pair up the vertices by using the edges (of the Petersen graph) between the inner and the outer pentagons, and color each pair with one color. So now we need to check for possible 4-colorings… – A.Sh Oct 29 '15 at 21:44
• The complement of the Petersen graph is the line graph of $K_5$, so you want the edge chromatic numer of $K_5$. – Chris Godsil Oct 30 '15 at 0:49