Upper bound on the chromatic number of an arbirary hypergraph

33 Views Asked by At

We consider a (proper; that is, there is no monochromatic edge $A\in E$) vertex coloring $f:V\to C$ of some hypergraph $H$. Suppose that $\Delta(H) = \max \mathrm{deg}\;v$. I am well aware that for a graph $G$ ($2$-regular hypergraph) the following inequality holds: $\chi(G)\leq \Delta(G) + 1$. This result is quite easy to prove, however, I wonder if the same holds for any hypergraph $H$? The same argument does not seem to be easily applied to this case. If it is true, then how does one proceed with the proof?