tailieunhanh - Báo cáo toán học: "Note on highly connected monochromatic subgraphs in 2-colored complete graphs"

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: Note on highly connected monochromatic subgraphs in 2-colored complete graphs. | Note on highly connected monochromatic subgraphs in 2-colored complete graphs Shinya Fujita Colton Magnanh Submitted Jul 25 2009 Accepted Nov 13 2009 Published Jan 12 2011 Mathematics Subject Classification 05C15 05C40 Abstract In this note we improve upon some recent results concerning the existence of large monochromatic highly connected subgraphs in a 2-coloring of a complete graph. In particular we show that if n k 1 then in any 2-coloring of the edges of Kn there exists a monochromatic k-connected subgraph of order at least n 2 k 1 . Our result improves upon several recent results by a variety of authors. 1 Introduction It is easy to see that for any graph G either G or its complement is connected. This is equivalent to saying there exists a connected color in any 2-coloring of Kn. However when we try to find a subgraph with higher connectivity we cannot hope to find such a spanning subgraph. In order to see this consider the following example. All standard notation comes from 3 . Consider the following example from 1 . Let Gn H1 u u H5 where Hi is a red complete graph Kk-i for i 4 and H5 is a red Kn-4 k-1 where n 4 k 1 . To this structure we add all possible red edges between H5 H1 and H2 and from H1 to H3 and from H2 to H4. All edges not already colored in red are colored in blue. In either color there is no k-connected subgraph of order larger than n 2 k 1 . Since a spanning monochromatic subgraph is more than we could hope for we consider finding a highly connected subgraph that is as large as possible. Along this line Bollobas and Gyarfas proposed the following conjecture. Conjecture 1 1 For n 4 k 1 every 2-coloring of Kn contains a k-connected monochromatic subgraph with at least n 2 k 1 vertices. Department of Mathematics Gunma National College of Technology. 580 Toriba Maebashi Gunma Japan 371-8530. Supported by JSPS Grant No. 20740068 Department of Mathematics Lehigh University 27 Memorial Dr W. Bethlehem PA USA 18015.