2
$\begingroup$

Hello ladies and gentlemen.

This is Petersen Graph - enter image description here

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$.

$\endgroup$
  • $\begingroup$ 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… $\endgroup$ – A.Sh Oct 29 '15 at 21:44
  • 2
    $\begingroup$ The complement of the Petersen graph is the line graph of $K_5$, so you want the edge chromatic numer of $K_5$. $\endgroup$ – Chris Godsil Oct 30 '15 at 0:49
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm sorry, I'm rather new to graph theory and I'm unfamiliar with that term. $\endgroup$ – Rick Joker Oct 29 '15 at 21:44
  • $\begingroup$ 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. $\endgroup$ – Gregory J. Puleo Oct 29 '15 at 21:45
  • $\begingroup$ I think it's 3. If I understood you correctly. $\endgroup$ – Rick Joker Oct 29 '15 at 22:06
  • $\begingroup$ @RickJoker An independent set of size 3 in the complement would correspond to a triangle in the Petersen graph; does Pete have any triangles? $\endgroup$ – Gregory J. Puleo Oct 29 '15 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.