|
|||||
|
|
Highly connected monochromatic subgraphs |
|
| Authors: | Béla Bollobás András Gyárfás |
| Institution: | a Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA b Trinity College, Cambridge, CB2 1TQ, UK c Computer and Automation Research Institute of the Hungarian Academy of Sciences, P.O. Box 63, Budapest 1518, Hungary |
| Abstract: | We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph Kn contains a k-connected monochromatic subgraph with at least n-2(k-1) vertices. This conjecture, if true, is best possible. Here we prove it for k=2, and show how to reduce it to the case n<7k-6. We prove the following result as well: for n>16k every 2-colored Kn contains a k-connected monochromatic subgraph with at least n-12k vertices. |
| Keywords: | Edge coloring of complete graphs k-connected monochromatic subgraphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |