Four-vertex obstruction to polychromatic three-colouring
ID: four-vertex-obstruction-to-polychromatic-three-colouring
Take every three-element subset of a four-element vertex set as a hypergraph edge. Any three-colouring repeats a colour on two vertices. A triple containing that pair cannot contain all three colours. Thus this uniform hypergraph has no polychromatic three-colouring, although each edge meets only three other edges.
New to topics? Read the docs here!