首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号