### 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

Chudnovsky, M., Seymour, P., Spirkl, S., & Zhong, M. (2018). Triangle-free graphs with no six-vertex induced path.

*Discrete Mathematics*,*341*(8), 2179-2196. https://doi.org/10.1016/j.disc.2018.04.020