TAILIEUCHUNG - Báo cáo toán học: "Ramsey (K1,2, K3)-minimal graphs"

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 I. Schiermeyer Institut fur Diskrete Mathematik und Algebra Technische Universitat Bergakademie Freiberg 09596 Freiberg Germany schierme@ E. Sidorowicz Faculty of Mathematics Computer Science and Econometrics University of Zielona Góora Szafrana 4a 65-516 Zielona Gora Poland 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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã 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.