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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Wojowu Sep 17 '19 at 10:02
  • 2
    $\begingroup$ Correction: any infinite chromatically rigid graph. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.