Graphs with small chromatic numbers are easy to color
A polynomial time graph coloring algorithm is presented with the following property: there is a constant \(c>0\) such that if \(k=k(n)\) is a function such that \(k\leq \sqrt{c n/\log n}\), then the algorithm colors optimally almost all graphs with n vertices and chromatic number less than or equal to k.
scientific article; zbMATH DE number 4088949