Name
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). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2018.04.020 | Discrete Mathematics |
Keywords | Field | DocType |
Induced subgraph,Induced path | Discrete mathematics,Complete bipartite graph,Graph,Combinatorics,Vertex (geometry),Modulo,Induced path,Induced subgraph,Clebsch graph,Matching (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
341 | 8 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Paul D. Seymour | 2 | 2786 | 314.49 |
| Sophie Theresa Spirkl | 3 | 8 | 7.36 |
| Mingxian Zhong | 4 | 7 | 4.25 |