×

Ear decompositions in combed graphs. (English) Zbl 1180.05086

Summary: 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 L. Lovász and M.D. Plummer [Matching theory, Ann. Discrete Math. 29, North-Holland Mathematics Studies 121, Amsterdam, etc. (1986; Zbl 0618.05001)]. 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0618.05001
PDFBibTeX XMLCite
Full Text: EuDML EMIS