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
Fingerprint
Dive into the research topics of 'Triangle-free graphs with no six-vertex induced path'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver