We explore several classical constructions of triangle-free graphs with arbitrarily large chromatic number, including those due to Tutte, Mycielski, and the family of shift graphs. For each construction, we highlight key structural properties and distinguishing features. Building on previous work by Codenotti, Pudlák, and Resta, we introduce an explicit construction of a new, parametrized family of triangle-free graphs that generalizes their construction. For certain parameter choices, this family
achieves an independence number of order O(n²ᐟ³) and a chromatic number of order Ω(n¹ᐟ³) where n is the number of vertices, matching the best-known constructive bounds for triangle-free graphs. In addition, we revisit Erdős’s classical use of the probabilistic method to prove the existence of graphs with arbitrarily high girth and chromatic number, and we present a recent explicit construction achieving the same properties.
|
