Triangle-free graphs with no six-vertex induced path

Maria Chudnovsky, Paul Seymour, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)2179-2196
Number of pages18
JournalDiscrete Mathematics
Volume341
Issue number8
DOIs
StatePublished - 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