<p>Yes; they are known as <a href="http://www.graphclasses.org/classes/gc_394.html">$2K_2$-free graphs</a>. Some additional references:</p>

<ul>
<li>"<a href="http://dx.doi.org/10.1002/jgt.21734">On Toughness and Hamiltonicity of $2K_2$-Free Graphs</a>"</li>
<li>"<a href="http://dx.doi.org/10.1016/0012-365X(90)90144-7">The maximum number of edges in $2K_2$-free graphs of bounded degree</a>";</li>
<li>"<a href="http://dx.doi.org/10.1016/j.disc.2006.07.001">Two characterisations of minimal triangulations of $2_{K2}$-free graphs</a>"</li>
</ul>

CC BY-SA 3.0
2015-06-05T22:13:31.420Z
2015-06-05T22:13:31.420Z
David Eppstein
<p>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. </p>

CC BY-SA 3.0
2015-06-09T03:21:16.987Z
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.
Chandra Chekuri
<graph-theory>
Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Chandra Chekuri
# Structure of graphs that exclude a perfect matching on four vertices as an induced graph

(Asked by: username_0 on 2015-06-05)

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.

**Tags:** graph-theory

> **Comments:**
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2015-06-05. Score: 18 | Accepted answer

Yes; they are known as [$2K\_2$-free graphs](http://www.graphclasses.org/classes/gc_394.html). Some additional references:

* "[On Toughness and Hamiltonicity of $2K\_2$-Free Graphs](http://dx.doi.org/10.1002/jgt.21734)"
* "[The maximum number of edges in $2K\_2$-free graphs of bounded degree](http://dx.doi.org/10.1016/0012-365X(90)90144-7)";
* "[Two characterisations of minimal triangulations of $2\_{K2}$-free graphs](http://dx.doi.org/10.1016/j.disc.2006.07.001)"


---

