Matching Covered Graphs with Three Removable Classes

  • Marcelo H. de Carvalho
  • Charles H. C. Little
Keywords: graph theory, perfect matchings, matching covered graphs


The notion of removable classes arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. The last (single or double) ear of an ear decomposition is defined as a removable class. Every matching covered graph not induced by a circuit has at least three removable classes. In this paper, we characterize matching covered graphs with precisely three removable classes and show, as a corollary, that every non-planar matching covered graph has at least four removable classes. Let $G$ be a matching covered graph. A matching covered subgraph $H$ of $G$ is conformal if $G-VH$ has a perfect matching. Given $S \subseteq EG$, what is a minimal conformal subgraph of $G$ that contains $S$? It is known that if $|S|=2$ then it is induced by a circuit. As an application of the main result, we answer this question for $|S|=3$.

Article Number