1
$\begingroup$

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes which fit the bill.

Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Let $G$ be a $k$-regular graph with a 1-factorization. Then its line graph $L(G)$ is $k$-colorable and has cliques of size $k$, and so its complement will be in your class if it's not perfect. It will not be perfect if the girth of $G$ is five, because an induced 5-cycle in $G$ gives an induced 5-cycle in $L(G)$, and in its complement.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .