کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650246 1342481 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge-colorings avoiding rainbow and monochromatic subgraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Edge-colorings avoiding rainbow and monochromatic subgraphs
چکیده انگلیسی

For two graphs G and H  , let the mixed anti-Ramsey numbers, maxR(n;G,H)maxR(n;G,H), (minR(n;G,H))(minR(n;G,H)) be the maximum (minimum) number of colors used in an edge-coloring of a complete graph with n vertices having no monochromatic subgraph isomorphic to G and no totally multicolored (rainbow) subgraph isomorphic to H. These two numbers generalize the classical anti-Ramsey and Ramsey numbers, respectively.We show that maxR(n;G,H)maxR(n;G,H), in most cases, can be expressed in terms of vertex arboricity of H and it does not depend on the graph G  . In particular, we determine maxR(n;G,H)maxR(n;G,H) asymptotically for all graphs G and H, where G is not a star and H has vertex arboricity at least 3.In studying minR(n;G,H)minR(n;G,H) we primarily concentrate on the case when G=H=K3G=H=K3. We find minR(n;K3,K3)minR(n;K3,K3) exactly, as well as all extremal colorings. Among others, by investigating minR(n;Kt,K3)minR(n;Kt,K3), we show that if an edge-coloring of KnKn in k   colors has no monochromatic KtKt and no rainbow triangle, then n⩽2kt2n⩽2kt2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 20, 28 October 2008, Pages 4710–4723
نویسندگان
, ,