Return to Revisions

For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and for good reason. Using Toft's graph, one can apply the Mycielski construction to obtain triangle-free $k$-critical graphs for all $k \geq 4$. A different and (optimally dense) construction of triangle-free $k$-critical graphs was obtained by Pegden.