# Chromatic number of $C_4$-free graphs

How large can the chromatic number of an $$n$$-vertex $$C_4$$-free graph be? If the maximum degree of the graph $$G$$ is $$\Delta$$, is there a bound of the form $$\chi(G) \leq O(\Delta/\log(\Delta))$$ as in the case of triangles? What happens if $$e(G)$$ is close to $$ex(n,C_4)$$, say $$e(G) \geq n^{3/2-\alpha}$$; is there a better bound (depending on $$\alpha$$) in this case?

For $$G$$ an $$n$$ vertex graph which is $$C_4$$-free, $$\chi(G)=O(\sqrt{n})$$, follows from Kővári–Sós–Turán by the argument found here for instance.

Before Johannson proved the chromatic number bound for triangle free graphs, the inequality appeared in a paper of Kim as a conjectured improvement to the girth $$>4$$ case. In that case, the inequality is due to Kim and takes the form

$$\chi(G)≤[1 +o(1)]\frac{\Delta}{\log \Delta},$$

where the $$o(1)$$ is taken as $$\Delta(G)\rightarrow\infty$$. For the case that $$G$$ is $$C_4$$ saturated, or nearly so, there is less which appears immediately in a quick search.

• Does the arguments apply to $C_4$-free graph with triangles? – Bullet51 Jun 16 at 8:01
• "For the case that G is C4 saturated, or nearly so, there is less which appears immediately in a quick search." Can you please refer me to this paper? – Lior Gishboliner Jun 16 at 8:04
• Actually I didn't know about the Kim paper. I am most interested in the case that $e(G)$ is close to $ex(n,C_4)$. Perhaps I should have phrased my question accordingly. – Lior Gishboliner Jun 16 at 8:13
• For the equality case, with polarity graphs, it’s known that the extremal graph is unique (Furedi) and its chromatic number is about n^1/4. I would guess this is also true close to equality, but this if true should be very hard. – user36212 Jun 16 at 12:31
• Is it feasible to prove that near equality, the chromatic number is significantly below the trivial bound of $n^{1/2}$, or the known bound of $n^{1/2}/\log(n)$? (without insisting to get $n^{1/4}$). – Lior Gishboliner Jun 16 at 12:56