Triangle-free graphs with no six-vertex induced path
Abstract
The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).
Collections
Cite this version of the work
Maria Chudnovsky, Paul Seymour, Sophie Spirkl, Mingxian Zhong
(2018).
Triangle-free graphs with no six-vertex induced path. UWSpace.
http://hdl.handle.net/10012/18513
Other formats
The following license files are associated with this item: