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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
-
1$\begingroup$ Does the arguments apply to $C_4$-free graph with triangles? $\endgroup$LeechLattice– LeechLattice2019-06-16 08:01:05 +00:00Commented Jun 16, 2019 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– Lior Gishboliner2019-06-16 08:04:10 +00:00Commented Jun 16, 2019 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– Lior Gishboliner2019-06-16 08:13:11 +00:00Commented Jun 16, 2019 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– user362122019-06-16 12:31:55 +00:00Commented Jun 16, 2019 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– Lior Gishboliner2019-06-16 12:56:54 +00:00Commented Jun 16, 2019 at 12:56
$\begingroup$
$\endgroup$
For the second question with respect to maximum degree, a bound of the desired form was first observed by Alon, Krivelevich and Sudakov (see https://doi.org/10.1006/jctb.1999.1910, Cor 2.4). My colleagues and I showed a tighter bound of this form (see https://arxiv.org/abs/2003.14361, Thm 4).
Edit on 25 September 2023: Further to the $O(\Delta/\log\Delta)$ bound of Alon-Krivelevich-Sudakov, Matthieu Rosenfeld and I recently conjectured that the chromatic number of any $C_4$-free graph of maximum degree at most $\Delta$ is at most $\lceil (\Delta+1)/2\rceil+1$. (Of course this is "only" open for finitely many values of $\Delta$.)
