Name
Abstract | ||
|---|---|---|
We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph K"n 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 K"n contains a k-connected monochromatic subgraph with at least n-12k vertices. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disc.2006.01.030 | Discrete Mathematics |
Keywords | Field | DocType |
k-connected monochromatic subgraphs,edge coloring of complete graphs,edge coloring,complete graph | Reconstruction conjecture,Discrete mathematics,Complete graph,Combinatorics,Monochromatic color,Vertex (geometry),Graph colouring,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
308 | 9 | Discrete Mathematics |
Citations | PageRank | References |
13 | 1.54 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| András Gyárfás | 2 | 582 | 102.26 |