کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902913 1632396 2018 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Triangle-free graphs with no six-vertex induced path
ترجمه فارسی عنوان
نمودارهای بدون مثلث بدون مسیر شش ارگانیک
کلمات کلیدی
زیرگرافی منجر شده، مسیر منجر شده،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
, , , ,