3 citations · 7 across the 10 of their papers we have counts for
Showing 2008 · math.COShow all
3 papers · 2 filters
math.CO2008
On the chromatic number of random d-regular graphs
Graeme Kemkes, Xavier Pérez-Giménez, Nicholas Wormald
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)…
math.CO2008
High degree graphs contain large-star factors
Noga Alon, Nicholas Wormald
We show that any finite simple graph with minimum degree contains a spanning star forest in which every connected component is of size at least . This sett…
math.CO2008★ 1 cited
Regular induced subgraphs of a random graph
Michael Krivelevich, Benny Sudakov, Nicholas Wormald
An old problem of Erdős, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, w…