# Chromatic number of complement of Petersen graph

Hello ladies and gentlemen.

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

## 1 Answer

Hint: what's the independence number of the complement?

• I'm sorry, I'm rather new to graph theory and I'm unfamiliar with that term. – Rick Joker Oct 29 '15 at 21:44
• The independence number of a graph is the largest size of an independent set. An independent set is a set of vertices that are pairwise nonadjacent. – Gregory J. Puleo Oct 29 '15 at 21:45
• I think it's 3. If I understood you correctly. – Rick Joker Oct 29 '15 at 22:06
• @RickJoker An independent set of size 3 in the complement would correspond to a triangle in the Petersen graph; does Pete have any triangles? – Gregory J. Puleo Oct 29 '15 at 22:26