## Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be the maximum number of hyperedges containing any vertex. Let $\omega$ be the maximum size of a clique, meaning a vertex set such that for every pair of vertices in the clique, some edge contains both.

Question: is there $\epsilon>0$ so that $\chi \le \Delta \omega / (1+\epsilon)$ in all hypergraphs?

Motive: let $R$ be the maximum edge size. A simple greedy algorithm for colouring can be used to establish that $\chi \le 1 + \Delta(R-1)$, and this bound cannot be improved in general. Note $\chi \ge \omega \ge R$; so I am essentially asking if $\omega$ approximates $\chi$ more closely than $R$.

-

Given a hypergraph $H$, form a graph $G$ by replacing all hyperedges by cliques. Than $\chi(G)=\chi$, $\omega(G)=\omega$ and $\Delta(G)\le\Delta(R-1)$. Bruce Reed, in his paper "$\omega$, $\Delta$ and $\chi$", J. Graph Theory 27 (1998) 177-212, proves that if $a=1/140000000$, then for $\Delta(G)$ large enough, we have $\chi(G)\le a\omega(G)+(1-a)(\Delta(G)+1)$. So for the hypergraph we have $$\chi\le a\omega+(1-a)(\Delta(R-1)+1)\le a\omega+(1-a)\Delta R\le a\omega+(1-a)\Delta\omega=(1-a+a/\Delta)\cdot\Delta\omega.$$ So if $\Delta\ge2$ (and $\Delta(R-1)$ large enough to allow Bruce's theorem), we get $\chi\le(1-a/2)\Delta\omega$.
 That's great! That totally answers the original question as far as I can see, assuming $\Delta, R \ge 2$ (and I notice now my conjecture was false for $\Delta = 1$), since for bounded $\Delta(R-1)$ we must have that $\Delta$ and $R$ are bounded, in which case $\Delta(R-1)+1$ is indeed at most $\Delta\omega/(1+\epsilon)$. – Dave Pritchard Jan 24 2011 at 19:10 Just for the record, Bruce and I now have an easier proof of this theorem posted on arXiv, but it still uses a combination of structural and probabilistic arguments. – Andrew D. King Jan 15 at 13:09