2
$\begingroup$

A hypergraph is intersecting if every two edges contain at least one common vertex. I read in a paper that for all intersecting hypergraphs, we need at most either two or three colors in order to color every vertex so that there are no monochromatic edges. This fact was stated as "obvious." Can someone offer a proof of this fact (or help me write a proof of this fact)?

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

This is indeed true under the assumption the hypergraph $H$ you consider is finite (or even just that there is an inclusionwise minimal edge) and all edges of $H$ have size at least $2$ (otherwise some edge has to be monochromatic). First, $2$-colour the vertices in an inclusionwise minimal edge $e$ of $H$, and use a third colour on the remaining vertices. Then $e$ is not monochromatic, and any other edge has vertex in $e$ and a vertex not in $e$, so no edge of $H$ is monochromatic. We might not always need 3 colours, but sometimes this is necessary, for instance, a triangle in the graph sense is intersecting, and has chromatic number $3$.

$\endgroup$
1
  • 2
    $\begingroup$ More generally, an intersecting hypergraph $H=(V,E)$ is $3$-colourable if and only if the collection $\mathcal U=\{U\subseteq V:\exists e\in E,\ e\subseteq U\}$ is not an ultrafilter on $V$. $\endgroup$
    – bof
    Commented Jan 24 at 4:28