tailieunhanh - Báo cáo toán học: "Upper and lower bounds for Fv (4, 4; 5)"

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:Upper and lower bounds for Fv (4, 4; 5). | Upper and lower bounds for Fv 4 4 5 Xiaodong Xu Haipeng Luo Guangxi Academy of Sciences Nanning 530007 China xxdmaths@ haipengluo@ Zehui Shao Key Laboratory of Pattern Recognition and Intelligent Information Processing School of Information Science Technology Chengdu University Chengdu 610106 China kidszh_mail@ Submitted Jun 23 2010 Accepted Sep 29 2010 Published Oct 22 2010 Mathematics Subject Classifications 05C55 Abstract In this note we give a computer assisted proof showing that the unique 5 3 -Ramsey graph is the unique K5-free graph of order 13 giving Fv 3 4 5 13 then we prove that 17 Fv 2 2 2 4 5 Fv 4 4 5 23. This improves the previous best bounds 16 Fv 4 4 5 25 provided by Nenov and Kolev. 1 Introduction In this note we shall only consider graphs without multiple edges or loops. If G is a graph then the set of vertices of G is denoted by V G the set of edges of G by E G the cardinality of V G by V G and the complementary graph of G by G. The subgraph of G induced by S c V G is denoted by G S . A cycle of order n is denoted by Cn. Given a positive integer n Zn 0 1 2 n 1 and S c 1 2 _n 2_ let G be a graph with the vertex set V G Zn and the edge set E G x y min x y n x y G S then G is called a cyclic graph of order n denoted by Gn S . G is an s t -graph if G contains neither clique of order s nor independent set of order t. We denote by R s t the set of all s t -graphs. An s t -graph of order n is called an s t n -graph. We denote by R s t n the set of all s t n -graphs. The Ramsey number R s t is defined to be the minimum number n for which R s t n is not empty. In 3 it was proved that R 4 3 9 and R 5 3 14 which are useful in the following. For a graph G and positive integers a1 a2 ar we write G a1 a2 vr v if every r-coloring of the vertices must result in a monochromatic aj-clique of color i for THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N34 1 some i G 1 2 r . Let Fv a1 a2 ar k G G 1 a2 ar v and Kk G G . The graphs in Fv a1 a2 ar