Spanning Eulerian Subgraphs in Claw-free graphs

Zhi-Hong Chen1, Hong-Jian Lai2, Weiqi Luo3, Yehong Shao4
1Butler University, Indianapolis, IN 46208
2West Virginia University, Morgantown, WV 26506
3JiNan University, Guangzhou, P.R. China
4Arts and Sciences, Ohio University Southern, Ironton, OH 45638

Abstract

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 graph has a spanning Eulerian subgraph with maximum degree at most 4.