Star Coloring of Hypergraphs

Abstract

We study a generalization of the star coloring problem on hypergraphs. For a family of connected subhypergraphs $\mathcal{F}$, we define an $\mathcal{F}$-coloring of a hypergraph as a coloring avoiding monochromatic hyperedges and any 2-colored member of $\mathcal{F}$. We let ${\chi }_{\mathcal{F}}^r(d)$ be the maximum of the minimum number of colors needed for an $\mathcal{F}$-coloring of an $r$-uniform hypergraph with maximum degree $d.$ We show bounds for ${\chi }_{\mathcal{F}}^r(d)$, that also yield results on star and acyclic coloring problem on hypergraphs.