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!