13
$\begingroup$

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.

$\endgroup$
  • $\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$ – Chandra Chekuri Jun 9 '15 at 3:21
18
$\begingroup$

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

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