Spanning Eulerian Subgraphs in Claw-Free Graphs

Zhi-Hong Chen 1, Hong-Jian Lai 2, and Weiqi Luo 3,
1 Butler University, Indianapolis, IN 46208, USA
2 West Virginia University, Morgantown, WV 26506, USA
3 West Jinan University, Guangzhou, P. R. China

Abstract     Full Text  PDF

A graph is claw-free if it has no induced $K_{1,3}$ subgraph. A graph is essential 4-edge-connected if removing at most three edges, the resulting graph has at most one component having edges. In this note, we show that every essential 4-edge-connected claw free simple graph has a spanning Eulerian subgraph with maximum degree at most 4.