I am interested in understanding the structure of the class of graphs $G$ such that there is no vertex induced subgraph on four vertices that is a perfect matching. Stated differently for any four vertices $a,b,c,d$ in $G$ if $ab$ and $cd$ are edges then the graph should have at least one more edge on the four vertices. Has this class been studied previously? Any references or insights would be appreciated. We understand this class when restricted to bipartite graphs but the general case seems more tricky.

  • $\begingroup$ Want to add here an important property of the $2K_2$-free graphs, namely that the number of maximal independent sets in such graphs is polynomial in the number of vertices. In fact for any fixed $t$ $tK_2$-free graphs have a polynomial number of maximal independent sets. See following ref for more information. "Complexity results on graphs with few cliques." Discrete Mathematics and Theoretical Computer Science 9.1 (2007): 127-135. $\endgroup$ Commented Jun 9, 2015 at 3:21

1 Answer 1


Yes; they are known as $2K_2$-free graphs. Some additional references:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.