Triangle-free graphs with no six-vertex induced path |
| |
Authors: | Maria Chudnovsky Paul Seymour Sophie Spirkl Mingxian Zhong |
| |
Institution: | 1. Princeton University, Princeton, NJ 08544, United States;2. Columbia University, New York, NY 10027, United States |
| |
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 subgraph Induced path |
本文献已被 ScienceDirect 等数据库收录! |
|