کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647452 1342352 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rainbow C3C3’s and C4C4’s in edge-colored graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Rainbow C3C3’s and C4C4’s in edge-colored graphs
چکیده انگلیسی

Let GcGc be a graph of order nn with an edge coloring CC. A subgraph FF of GcGc is rainbow if any pair of edges in FF have distinct colors. We introduce examples to show that some classic problems can be transferred into problems on rainbow subgraphs. Let dc(v)dc(v) be the maximum number of distinctly colored edges incident with a vertex vv. We show that if dc(v)>n/2dc(v)>n/2 for every vertex v∈V(Gc)v∈V(Gc), then GcGc contains at least one rainbow triangle. The bound is sharp. We also obtain a new result about directed C4C4’s in oriented bipartite graphs and by using it we prove that if HcHc is a balanced bipartite graph of order 2n2n with an edge coloring CC such that dc(u)>3n5+1 for every vertex v∈V(Hc)v∈V(Hc), then there exists a rainbow C4C4 in HcHc.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 19, 6 October 2013, Pages 1893–1896
نویسندگان
,