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).
Original language | English (US) |
---|---|
Pages (from-to) | 2179-2196 |
Number of pages | 18 |
Journal | Discrete Mathematics |
Volume | 341 |
Issue number | 8 |
DOIs | |
State | Published - Aug 2018 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Keywords
- Induced path
- Induced subgraph