Random I‐colorable graphs
Hans Jürgen Prömel, Angelika Steger · Random Structures and Algorithms · 1995
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 G l n denote a uniformly chosen element of this class, i.e., a random l ‐colorable graph. For a random graph G l n 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.