Random I-colorable graphs |
| |
Authors: | Hans Jürgen Prmel Angelika Steger |
| |
Institution: | Hans Jürgen Prömel,Angelika Steger |
| |
Abstract: | In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let Gln denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph Gln we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges. |
| |
Keywords: | |
|
|