Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902913 | Discrete Mathematics | 2018 | 18 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maria Chudnovsky, Paul Seymour, Sophie Spirkl, Mingxian Zhong,