کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652690 1632601 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Totally Multicolored diamonds
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Totally Multicolored diamonds
چکیده انگلیسی

Let G be a graph of order p. For every n≥p let f(n,G) be the minimum integer k such that for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors. Let F be a set of graphs. For every n≥3 let ext(n,F) be the maximum number of edges of a graph on n vertices with no subgraph isomorphic to an element of F. Here we study the relation between f(n,G) and ext(n,C(G)) when G is a graph with chromatic number 3 obtained by adding an edge (a chord) to a cycle, and C(G) is the set of cycles which are subgraphs of G. In particular, an upperbound and a lowerbound of f(n,G) are given; and in the case when G is the diamond (C4 with a chord), we prove that the supremum and infimum limits of are bounded by and respectively, and we conjecture that for every n≥4, f(n,G)=ext(n,{C3,C4})+2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 30, 20 February 2008, Pages 231-236