Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic number, $\Delta$ is the maximum degree, and $\omega$ is the clique number.

Is there any similar theorem or conjecture that has to do with hypergraph colorings? That is where the vertices can be colored in $\chi$ colors such that no edge is monochromatic.

More helpful for me is the case of coloring where every k-edge has k different colors (Rainbow coloring).


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.