کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647452 | 1342352 | 2013 | 4 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 313, Issue 19, 6 October 2013, Pages 1893–1896