کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777056 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On Induced Colourful Paths in Triangle-free Graphs
ترجمه فارسی عنوان
در مسیر های رنگارنگ منجر شده در نمودارهای بدون مثلث
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسیر منجر شده، مسیر رنگارنگ، نمودار بدون مثلث،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on Ï(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on Ï(G) vertices and prove its correctness when the girth of G is at least Ï(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if Ï(G)â¥f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 69-75
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 69-75
نویسندگان
Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis,