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{10_37236_2657,
author = {Marcelo H. de Carvalho and Charles H. C. Little},
title = {Matching covered graphs with three removable classes},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/2657},
zbl = {1300.05249},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2657/}
}
TY - JOUR
AU - Marcelo H. de Carvalho
AU - Charles H. C. Little
TI - Matching covered graphs with three removable classes
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2657/
DO - 10.37236/2657
ID - 10_37236_2657
ER -
%0 Journal Article
%A Marcelo H. de Carvalho
%A Charles H. C. Little
%T Matching covered graphs with three removable classes
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2657/
%R 10.37236/2657
%F 10_37236_2657
Marcelo H. de Carvalho; Charles H. C. Little. Matching covered graphs with three removable classes. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/2657
