1
$\begingroup$

As I understand, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Should I show, that chromatic numbers of all Petersen's subgraphs are not equal to it clique number? Maybe there is an easier and quickly way to show that.

$\endgroup$
1
$\begingroup$

The Petersen graph is a Kneser graph, precisely $\text{KG}(5,2)$. By Lovasz theorem the chromatic number of $\text{KG}(n,k)$ is $n-2k+2$, hence in our case $\chi(G)=3$. On the other hand $5<6$, hence the Petersen graph is triangle-free.

$\endgroup$
  • $\begingroup$ Is there any theorem, that perfect graph can't be triangle-free? $\endgroup$ – Rijndael Feb 1 '17 at 20:32
  • $\begingroup$ Using the Lovasz theorem on Kneser graphs seems like major overkill. The Peterson graph contains an induced pentagon, qed. $\endgroup$ – Nate Feb 1 '17 at 20:32
  • $\begingroup$ @Nate: I agree with you. I was just in the mood of killing mosquitoes with atomic bombs. $\endgroup$ – Jack D'Aurizio Feb 1 '17 at 20:52
0
$\begingroup$

Check out this link --- it shows the clique number is less than the chromatic number of the entire graph.

http://mathworld.wolfram.com/PetersenGraph.html

$\endgroup$
  • $\begingroup$ Thanks, I saw it. But, I didn't clearly understand where the proof, that the clique number is less $\endgroup$ – Rijndael Feb 1 '17 at 20:29

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.