Finding a spanning Halin subgraph in 3-connected \(\{K_{1,3},P_5\}\)-free graphs

Suil O

Georgia State University, USA

Georgia State University, USA

2014/08/28 *Thursday* 4PM-5PM

Room 1409

Room 1409

A Halin graph is constructed from a plane embedding of a tree whose non-leaf vertices have degree at least 3 by adding a cycle through its leaves in the natural order determined by the embedding. In this talk, we prove that every 3-connected \(\{K_{1,3},P_5\}\)-free graph has a spanning Halin subgraph. This result is best possible in the sense that the statement fails if \(K_{1,3}\) is replaced by \(K_{1,4}\) or \(P_5\) is replaced by \(P_6\). This is a joint work with Guantao Chen, Jie Han, Songling Shan, and Shoichi Tsuchiya.

Tags: 오수일