On the chromatic number of random d-regular graphs
| dc.creator | Kemkes, Graeme | |
| dc.creator | Pérez-Giménez, Xavier | |
| dc.creator | Wormald, Nicholas | |
| dc.date | 2008-12-15 | |
| dc.date.accessioned | 2026-07-07T12:13:00Z | |
| dc.date.available | 2026-07-07T12:13:00Z | |
| dc.description | In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k-1)log(k-1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k-1 or k. If moreover d>(2k-3)log(k-1), then the value k-1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of balanced k-colourings, where a colouring is balanced if the number of vertices of each colour is equal. | |
| dc.identifier | https://arxiv.org/abs/0812.2937 | |
| dc.identifier | http://arxiv.org/abs/0812.2937 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210732 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | On the chromatic number of random d-regular graphs | |
| dc.type | text |