2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2019 at 10:02
  • 2
    $\begingroup$ Correction: any infinite chromatically rigid graph. $\endgroup$
    – Wojowu
    Sep 17, 2019 at 10:12

1 Answer 1

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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