Large cliques in graphs with high chromatic number (Q6091811)

Let \(G\) be a simple graph. The maximum number of vertices that induces a complete subgraph of \(G\) is the clique number \(\omega (G)\). The biggest cardinality of an open neighborhood of a vertex from \(G\) is the maximum degree \(\Delta(G)\) of \(G\). A \(k\)-coloring of \(G\) is a map \(c:V(G)\rightarrow\{1,\dots,k\}\) where \(c(v)\neq c(u)\) for any \(uv\in E(G)\). The chromatic number \(\chi(G)\) of \(G\) is the maximum integer \(k\) such that there exists a \(k\)-coloring of \(G\). It is a simple observation that \(\omega(G)\leq \chi(G)\leq \Delta(G)+1\). There is a huge number of publications that consider relations between the three mentioned invariants as well as several conjectures about them. In particular, what can we say about a lower bound of \(\omega(G)\), if \(\chi(G)\) is close to \(\Delta(G)\)? This work brings an additional piece to this puzzle, by showing that \(\omega(G)\geq\Delta(G)-2t^2-6t-3\) whenever \(\chi(G)=\Delta(G)-t\) and \(\Delta(G)\geq 6t^2+20t+16\). To prove this, the authors relate to the improved use of Mozhan partitions of \(G\).