摘要
Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A（G） edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A（G） - 2 removable edges, where A（G） denotes the maximum degree of G. 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 K2 and C2n has at least x′（G） edge-disjoint removable ears, and any brick G distinct from Ka and Ce has at least x′（G） - 2 removable edges, where x′（G） denotes the edge-chromatic number of G. Key words 1-extendable graphs, removable ear, removable edge.
基金
supported by the National Science Foundation of China under Grant No.10831001
the Fujian Provincial Department of Education under Grant No.JA08223
