# Chromatically rigid hypergraphs

If $$H=(V,E)$$ is a hypergraph and $$\kappa$$ is a cardinal, then $$c:V\to\kappa$$ is a coloring if for every $$e\in E$$ with $$|e|>1$$, the restriction $$c|_e:e \to \kappa$$ is non-constant. By $$\chi(H)$$ we denote the smallest cardinal $$\kappa$$ such that there is a coloring $$c:V\to \kappa$$. We say that a hypergraph $$H=(V,E)$$ is chromatically rigid if $$\chi(H) = |V|$$.

If $$H=(V,E)$$ is chromatically rigid, is there always $$E_0\subseteq E$$ such that $$(V,E_0)$$ is chromatically rigid, and $$E_0$$ is $$\subseteq$$-minimal with respect to this property?

• It has occured to me that the reasoning as in my comment seems to apply to any chromatically rigid graph. Do you have an example where $E_0$ does exist? – Wojowu Sep 17 '19 at 10:02
• Correction: any infinite chromatically rigid graph. – Wojowu Sep 17 '19 at 10:12

Let $$H$$ be a complete graph on $$V=\omega$$. Suppose $$E_0$$ existed. Then removing a single edge would give a finitely colorable graph. Adding this edge back, we can color the graph with at most one more color. Same should work for any infinite $$V$$.