@article{f9d303f6b05040e58675421ee9496fe8,
title = "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).",
keywords = "Induced path, Induced subgraph",
author = "Maria Chudnovsky and Paul Seymour and Sophie Spirkl and Mingxian Zhong",
note = "Funding Information: The authorswould like to thank both referees for carefully reading the paper and suggesting a number of improvements. This material is based upon work supported by, or in part by, the U.S. Army Research Laboratory and the U. S. Army Research Office under contract/grant number W911NF-16-1-0404, and supported by NSF Grant DMS-1550991. The second author was supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563. Funding Information: The authorswould like to thank both referees for carefully reading the paper and suggesting a number of improvements. This material is based upon work supported by, or in part by, the U.S. Army Research Laboratory and the U. S. Army Research Office under contract/grant number W911NF-16-1-0404 , and supported by NSF Grant DMS-1550991 . The second author was supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563 . Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",
year = "2018",
month = aug,
doi = "10.1016/j.disc.2018.04.020",
language = "English (US)",
volume = "341",
pages = "2179--2196",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "8",
}