Removable Ears of 1-Extendable Graphs

Shaohui Zhai and Xiaofeng Guo
School of Mathematical Sciences, Xiamen University, Xiamen Fujian 361005, P.R. China


Abstract     Full Text  PDF

Carvalho, Lucchesi and Murty proved that any 1-extendable graph $G$ different from $K_2$ and $C_{2n}$ has at least $\Delta(G)$ edge-disjoint removable ears,and any brick $G$ distinct from $K_4$ and $\overline{C_6}$ has at least $\Delta(G)-2$ removable edges, where $\Delta(G)$ denotes the maximum degree of $G$. The former shows that any 1-extendable graph $G$ has at least $(\Delta(G))!$ distinct ear decompositions and thus is a generalization of the fundamental theorem of
Lov\'{a}sz and Plummer on the existence of ear decompositions, and the later generalizes a well-known theorem of Lov\'{a}sz. In this paper, we improve the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs. It is proved that any 1-extendable graph $G$ different from $K_2$ and $C_{2n}$ has at least $\chi'(G)$ edge-disjoint removable ears, and any brick $G$ distinct from $K_4$ and $\overline{C_6}$ has at least $\chi'(G)-2$ removable edges, where $\chi'(G)$ denotes the edge-chromatic number of $G$.