63 citations · 189 across the 26 of their papers we have counts for
Showing 2008 · math.COShow all
3 papers · 2 filters
math.CO2008★ 26 cited
The t-improper chromatic number of random graphs
Ross J. Kang, Colin McDiarmid
We consider the -improper chromatic number of the Erd{\H o}s-R{é}nyi random graph . The t-improper chromatic number of is the smallest number of colours nee…
math.CO2008★ 1 cited
The t-stability number of a random graph
Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid
Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the ma…
math.CO2008★ 7 cited
List Colouring Squares of Planar Graphs
Frédéric Havet, Jan van den Heuvel, Colin McDiarmid +1
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph with maximum degree is at most . We show t…