Premium
Random I‐colorable graphs
Author(s) -
Prömel Hans Jürgen,
Steger Angelika
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060104
Subject(s) - combinatorics , mathematics , random regular graph , random graph , graph , chromatic scale , discrete mathematics , class (philosophy) , chordal graph , 1 planar graph , computer science , artificial intelligence
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.