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
A **triangle-free graph** is a type of graph that does not contain any cycles of length three, which means it does not have any set of three vertices that are mutually connected by edges. In other words, if you pick any three vertices in the graph, at least one pair of those vertices will not be directly connected by an edge. Triangle-free graphs can be characterized using graph theory, and they have significant implications in various areas, including combinatorics, algorithm design, and social networks.