@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",

}