Choose and a binomial random graph of edge probability . With high probability its maximum degree is at most , it has triangles, and every independent set has size at most . Delete one vertex per triangle. The resulting triangle-free graph has chromatic number at least . Appending a disjoint star of degree , if necessary, makes the maximum degree exactly without lowering the chromatic number. Thus the order is unavoidable.
Articles by others on the same topic
There are currently no matching articles.