Triangle-free chromatic lower bound at bounded maximum degree
ID: triangle-free-chromatic-lower-bound-at-bounded-maximum-degree
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.
New to topics? Read the docs here!