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

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

$\endgroup$

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.