Consider a triangle-free graph $G$, in which the vertices are partitioned in blocks $V = A_1 \sqcup \dots \sqcup A_k$.

$G$ has the property that, for each $i \leq j$, each vertex in $A_i$ has at most $d 2^{i-j}$ neighbors in $A_j$.

What can be said about the chromatic number $\chi(G)$?

It is simple to see that $\chi(G) \leq O(d)$ (simply color all the vertices in $A_k$ in a greedy manner, than all the vertices in $A_{k-1}$, etc.)

I can show that $\chi(G) \leq O(\frac{d \log \log d}{\log d})$, as follows. Let $s = \log \log d$. Partition the vertices into groups $B_i = A_i \cup A_{s+i} \cup A_{2s + i} \cup \dots$ for $i = 1, \dots, s$.

We now claim $\chi(B_i) \leq O( \frac{d}{\log d})$. To see that this is true, we suppose that each vertex has an available color palette of size $c \frac{d}{\log d}$ where $c$ is a sufficiently large constant.

Start at the largest value $j s+i$, and color $G[A_{j s + i}]$ using $O(d/\log d)$ colors (it has degree $d$ and is triangle free.) Now look at the graph $G[A_{(j-1) s + i}]$. Each vertex touches at most $d 2^{-s} = d/\log d$ already-colored vertices. So it has at least $\Omega(\frac{d}{\log d})$ colors remaining in its palette. So it can be list-colored.

Continue this process to color $A_{(j-1) s + i}, A_{(j-2) s + i}, \dots, A_i$.

Is this bound tight? Can you obtain $\chi(G) \leq O( \frac{d}{\log d})$? (the factor of $\log \log d$ seems weird to me)

  • 1
    $\begingroup$ Maybe, even the following is true? If the graph does not have triangles and has $O(d\cdot |V_1|)$ edges inbetween any set $V_1\subset V$, then $\chi(G)=O(d/\log d)$? (Equivalent requirement is that the vertices of $G$ may be ordered so that each vertex has at most $O(d)$ vertices with greater number assigned. This is what we get if order each $A_i$ arbitrarily.) $\endgroup$ – Fedor Petrov Nov 18 '16 at 13:34
  • 3
    $\begingroup$ @FedorPetrov Your assumption is equivalent to graph having degeneracy $d$. Unfortunately, Johansson's theorem on chromatic number of triangle-free graphs fails for $d$-degenerate graphs. An example can be found in the concluding remarks of "Coloring graphs with sparse neighborhoods" by Alon, Krivelevich and Sudakov. $\endgroup$ – Boris Bukh Nov 21 '16 at 20:59

Your Answer

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

Browse other questions tagged or ask your own question.