Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Ramsey (K1,2, K3)-minimal graphs. | Ramsey K1 2 K3 -minimal graphs M. Borowiecki Faculty of Mathematics Computer Science and Econometrics University of Zielona Góra Szafrana 4a 65-516 Zielona Gora Poland m.borowiecki@wmie.uz.zgora.pl I. Schiermeyer Institut fur Diskrete Mathematik und Algebra Technische Universitat Bergakademie Freiberg 09596 Freiberg Germany schierme@math.tu-freiberg.de E. Sidorowicz Faculty of Mathematics Computer Science and Econometrics University of Zielona Góora Szafrana 4a 65-516 Zielona Gora Poland e.sidorowicz@wmie.uz.zgora.pl Submitted Jul 21 2004 Accepted Apr 14 2005 Published May 6 2005 Mathematics Subject Classifications 05C55 05C70 Abstract For graphs G F and H we write G F H to mean that if the edges of G are coloured with two colours say red and blue then the red subgraph contains a copy of F or the blue subgraph contains a copy of H. The graph G is F H -minimal Ramsey-minimal if G F H but G F H for any proper subgraph G0 c G. The class of all F H -minimal graphs shall be denoted by R F H . In this paper we will determine the graphs in R K12 K3 . 1 Introduction and Notation We consider finite undirected graphs without loops or multiple edges. A graph G has a vertex set V G and an edge set E G . We say that G contains H whenever G contains a subgraph isomorphic to H. The subgraph of G isomorphic to K3 we will call a triangle of G and sometimes denoted by its vertices. Let G1 G2 be subgraphs of G. We write G1 u G2 G1 n G2 for a subgraph of G with V G1 u G2 V G1 u V G2 and E G1 u G2 E G1 u E G2 V G1 n G2 V G1 n V G2 and E G1 n G2 E G1 n E G2 . THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R20 1 Let x and y be two nonadjacent vertices of G. Then G xy is the graph obtained from G by adding to G the edge xy. Let G F and H be graphs. We write G F H if whenever each edge of G is coloured either red or blue then the red subgraph of G contains a copy of F or the blue subgraph of G contains a copy of H. A graph G is F H -minimal Ramsey-minimal if G F H but G0 F H for any .