کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653431 | 1632771 | 2015 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge-colorings avoiding a fixed matching with a prescribed color pattern
ترجمه فارسی عنوان
لبه های رنگی اجتناب از تطبیق ثابت با الگوی رنگی تجویز شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We consider an extremal problem motivated by a question of ErdÅs and Rothschild (ErdÅs, 1974) regarding edge-colorings of graphs avoiding a given monochromatic subgraph. An extension of this problem to edge-colorings avoiding fixed subgraphs with a prescribed coloring has been studied by Balogh (Balogh, 2006). In this work, we consider the following natural generalization of the original ErdÅs-Rothschild question: given a natural number r and a graph F, an r-pattern P of F is a partition of the edge set of F into r (possibly empty) classes, and an r-coloring of the edge set of a graph G is said to be (F,P)-free if it does not contain a copy of F in which the partition of the edge set induced by the coloring has a copy of P. Let cr,(F,P)(G) be the number of (F,P)-free r-colorings of a graph G. For large n, we maximize this number over all n-vertex graphs for a large class of patterns in matchings and we describe the graphs that achieve this maximum.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 47, July 2015, Pages 75-94
Journal: European Journal of Combinatorics - Volume 47, July 2015, Pages 75-94
نویسندگان
Carlos Hoppen, Hanno Lefmann,