Upper bounds on the non-3-colourability threshold of random graphs.

Nikolaos Fountoulakis Colin McDiarmid

Published in: Discret. Math. Theor. Comput. Sci. (2002)

Keyphrases

random graphs
upper bound
lower bound
graph theoretic
learning curves
upper and lower bounds
lower and upper bounds
phase transition
vc dimension
undirected graph
small world
worst case
complex networks
tight upper and lower bounds
sample complexity
directed graph
power law
learning curve
efficiently computable