A graph $G$ is perfect if for all induced subgraphs $G'$, $\omega(G')=\chi(G')$.

A graph is normal if there exists a family of independent sets $A=\{A_1, A_2, \dots, A_p\}$ and a family of cliques $B=\{B_1,B_2,\dots,B_q\}$ such that $A_i \cap B_j \neq \emptyset$ for all $i,j$ and $A$ and $B$ both cover the vertex set.

I need to show that any given perfect graph is normal.

At first, I tried letting some perfect graph be given and construct the cliques and independent sets using the property of perfectness:

Given a perfect graph G, color it properly with $\chi(G)=\omega(G)=r$ colors. The goal was to let the color classes be the independent sets and adjust them during the following process. Take $B_1$ be the largest clique of $G$. Since $G$ is perfect, this clique intersects every given independent set. "Delete" this clique and take the next largest clique to construct $B_2$. If this clique does not intersect one of the color classes, then there are two cases: If one of the vertices is not incident to the missing color, then color that vertex the missing color as well. If every vertex is incident to the missing color, then I am stuck. If each vertex is incident to the same vertex colored the missing color, then that vertex can be included into the clique. However, if, say, there are two vertices with the missing color, each incident to half the clique, then I do not know how to go from there.

My next instinct was indction on edges, but there it is not always true that adding or removing and edge preserves perfectness.

Next was induction on vertices, but I have not even began to make any headway there.

Any ideas?


1 Answer 1


It can be shown that any graph such that every vertex is in a largest sized clique is normal by constructing the sets as you mentioned.

Then, you can use substitute edges for vertices in the same fashion as the substitution lemma (adjusting the sets accordingly) until you obtain any perfect graph whose largest clique is just as large as the largest clique you started with.

Hence, you can construct the sets by starting with a larger graph and substituting edges for vertices until you get any arbitrary perfect graph.

  • 1
    $\begingroup$ I think that's it. Thanks! $\endgroup$ May 14, 2019 at 14: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.