7
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Does the arguments apply to $C_4$-free graph with triangles? $\endgroup$ – LeechLattice Jun 16 at 8:01
  • $\begingroup$ "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? $\endgroup$ – Lior Gishboliner Jun 16 at 8:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Lior Gishboliner Jun 16 at 8:13
  • 2
    $\begingroup$ 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. $\endgroup$ – user36212 Jun 16 at 12:31
  • 1
    $\begingroup$ 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}$). $\endgroup$ – Lior Gishboliner Jun 16 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.