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$
$\endgroup$
1
-
$\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 ChekuriJun 9, 2015 at 3:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Yes; they are known as $2K_2$-free graphs. Some additional references:
answered Jun 5, 2015 at 22:13