کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776754 | 1413640 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
ترجمه فارسی عنوان
لبه های گراف از اجتناب از نمودار های کامل با رنگ های پیشنهادی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a graph F and an integer râ¥2, a partition FÌ of the edge set of F into at most r classes, and a graph G, define cr,FÌ(G) as the number of r-colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F. We think of FÌ as the pattern of coloring that should be avoided. The main question is, for a large enough n, to find the (extremal) graph G on n vertices which maximizes cr,FÌ(G). This problem generalizes a question of ErdÅs and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition FÌ contains a single class). We use Hölder's Inequality together with Zykov's Symmetrization to prove that, for any râ¥2, kâ¥3
and any pattern KkÌ of the clique Kk, there exists a complete multipartite graph that is extremal. Furthermore, if the pattern KkÌ has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r=3 and FÌ is a rainbow triangle (that is, where F=K3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r=3, we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2143-2160
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2143-2160
نویسندگان
FabrÃcio S. Benevides, Carlos Hoppen, Rudini M. Sampaio,