Ear Decompositions in Combed Graphs

Abstract

We introduce the concept of combed graphs and present an ear decomposition theorem for this class of graphs. This theorem includes the well known ear decomposition theorem for matching covered graphs proved by Lovász and Plummer. Then we use the ear decomposition theorem to show that any two edges of a 2-connected combed graph lie in a balanced circuit of an equivalent combed graph. This result generalises the theorem that any two edges in a matching covered graph with at least four vertices belong to an alternating circuit.