An equivalence condition of a graph being perfect.

25 Views Asked by At

For any simple graph $G$, define $t\left(G\right)$ be the smallest positive integer $t$ such that $G$ has $t$ independent sets and each vertex of $G$ appears in exactly two of these $t$ independent sets.

Prove that $G$ is a perfect graph if and only if $t\left(H\right)=2\chi\left(H\right)$ for any induced subgraph $H$ of $G$, where $\chi\left(H\right)$ is the chromatic number of $H$.

So far, I have proved that the ''only if '' part. Indeed, we have $$ t\left(H\right)\leq 2\chi\left(H\right)=2\omega\left(H\right)\leq t\left(H\right), $$ where $\omega\left(H\right)$ denote the maximal size of cliques in $H$.

However, I got stuck in showing the "if " part. I know that $2\omega\left(H\right)\leq 2\chi\left(H\right)= t\left(H\right)$ and $2\left| V\left(H\right)\right|\leq t\left(H\right)\cdot \alpha\left(H\right)$. But I can not go further.

Thanks in advanced.