|
In graph theory, a well-known observation of Erdős and Rado which is often considered as folklore; in fact it is also the first exercise in Béla Bollobás' book "Modern Graph Theory", is the following: For any graph, either it is connected, or its complement is connected. An equivalent formulation of the observation is the following: In any 2-colouring of the edges of a complete graph, one of the colours must induce a connected subgraph which spans all the vertices. In this talk, we shall generalise this result in many directions. For example, one direction would be to extend "2-colouring" above to "r-colouring", for any positive integer r. Then we can ask: "What is the largest possible order of a monochromatic, connected subgraph in any r-coloured complete graph?". Joint work with Robert Morris (University of Cambridge, England) and Noah Prince (University of Illinois at Urbana-Champaign, USA).
|
