Skip to main content
added 38 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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$-crticalcritical graphs for all $k \geq 4$. A different and (optimally dense) construction of triangle-free $k$-critical graphs was obtained by Pegden.

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$-crtical graphs for all $k \geq 4$. A different and (optimally dense) construction was obtained by Pegden.

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.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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$-crtical graphs for all $k \geq 4$. A different and (optimally dense) construction was obtained by Pegden.