The graphs of stably matchable pairs.
D. Eppstein.
arXiv:2010.09230.
47th International Workshop on Graph-Theoretic Concepts in Computer
Science (WG 2021).
Springer, Lecture
Notes in Comp. Sci. 12911 (2021), pp. 349–360, doi:10.1007/978-3-030-86838-3_27.
If you form a bipartite graph from a stable matching instance, with an edge for each pair that can participate in a stable matching, what graphs can you get? They are matching-covered, but \(\mathsf{NP}\)-hard to recognize, and their structure is related to the structure of the lattice of stable matchings of the same instance.
(WG'21 slides – Blog post: The graphs of stably matchable pairs)