tailieunhanh - Báo cáo toán học: "On multicolor Ramsey number of paths versus cycles"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On multicolor Ramsey number of paths versus cycles. | On multicolor Ramsey number of paths versus cycles Gholam Reza Omidi1 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156-83111 Iran and School of Mathematics Institute for Research in Fundamental Sciences Tehran 19395-5746 Iran romidi@ Ghaffar Raeisi Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156-83111 Iran Submitted Sep 5 2010 Accepted Jan 10 2011 Published Jan 26 2011 Mathematics Subject Classifications 05C15 05C55. Abstract Let G1 G2 . Gt be graphs. The multicolor Ramsey number R G1 G2 . Gt is the smallest positive integer n such that if the edges of a complete graph Kn are partitioned into t disjoint color classes giving t graphs H1 H2 . Ht then at least one Hi has a subgraph isomorphic to Gị. In this paper we provide the exact value of R Pni Pn2 . Pnt Ck for certain values of n and k. In addition the exact values of R P5 C4 Pk R P4 C4 Pk R P5 P5 Pk and R l l . l . are given. Finally we give a lower bound for R P2ni P2n2 . P2nt and we conjecture that this lower bound is the exact value of this number. Moreover some evidence is given for this conjecture. 1 Introduction In this paper we are only concerned with undirected simple finite graphs and we follow 1 for terminology and notations not defined here. The complement graph of a graph G is denoted by G. As usual the complete graph of order p is denoted by Kp and a complete bipartite graph with partite set X Y such that X m and Y n is denoted by Km n. Throughout this paper we denote a cycle and a path on m vertices by Cm and Pm respectively. Also for a 3-edge coloring say green blue and red of a graph G we denote by Gg resp. Gb and Gr the subgraph induced by the edges of color green resp. blue and red . 1This research was in part supported by a grant from IPM No. 89050037 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P24 1 Let G1 G2 . Gt be graphs. The multicolor Ramsey number R G1 G2 . Gt is the smallest .