![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Colin McDiarmid (University of Oxford)
Thursday 10 March 2016, 14:30-15:30
Clique colourings of random graphs
- đ¤ Speaker: Colin McDiarmid (University of Oxford)
- đ Date & Time: Thursday 10 March 2016, 14:30 - 15:30
- đ Venue: MR12
Abstract
A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number.
We shall discuss the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge probability p=p(n). We also discuss random geometric graphs, and see that with high probability the clique chromatic number is 2, when the threshold distance r is at least a modest constant factor above the threshold for connectivity. Finally, we see that the clique chromatic number is at most 14 for any geometric graph.
This is recent joint work with Dieter Mitsche and Pawel Pralat.
Series This talk is part of the Combinatorics Seminar series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- CMS Events
- Combinatorics Seminar
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- DPMMS Pure Maths Seminar
- Hanchen DaDaDash
- Interested Talks
- MR12
- School of Physical Sciences
Note: Ex-directory lists are not shown.