Connected subgraphs in multicoloured graphs
 
 
Description:  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).

 

Date:  2010-04-28
Start Time:   15:00
Speaker:  Henry Liu (FCT-CMA/FCTUNL)
Institution:  -
Place:  Room 5.5
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support