کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902913 | 1632396 | 2018 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Triangle-free graphs with no six-vertex induced path
ترجمه فارسی عنوان
نمودارهای بدون مثلث بدون مسیر شش ارگانیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زیرگرافی منجر شده، مسیر منجر شده،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2179-2196
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2179-2196
نویسندگان
Maria Chudnovsky, Paul Seymour, Sophie Spirkl, Mingxian Zhong,