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

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
4    19    1    06-07-2022
21    17    1    06-07-2022
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.