2
$\begingroup$

Let $H=(V,E)$ be a hypergraph. A coloring is a map $c:V\to \kappa$ where $\kappa\neq \emptyset$ is a cardinal, and the restriction $c\restriction_e:e\to \kappa$ is non-constant for every $e\in E$ with $|e|>1$. The chromatic number of H is the smallest cardinal $\kappa$ such that there is a coloring $c:V\to\kappa$.

If $S\subseteq V$, we let $\text{Gr}_H(S) = (S, E|_S)$ be the graph on $S$ having the edge set $$E|_S = \{\{s,t\}: s\neq t\in S \land (\exists e\in E(H)(s,t\in e))\}.$$

Question. If $H=(V,E)$ is a hypergraph such that $E\neq \emptyset$ and $|e|>1$ for all $e\in E$, is there $S\subseteq V$ with the following properties?

  1. $|S\cap e|\leq 2$ for all $e\in E$, and
  2. $\chi(\text{Gr}_H(S)) = \chi(H)$.
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Did you really mean to require that $|S\cap e|\le2$ for all $e\in E$? So if $H=(V,E)$ is a complete $3$-uniform hypergraph, $E=[V]^3$, you want $|S|\le2$? $\endgroup$
    – bof
    Commented May 19, 2021 at 11:25
  • 1
    $\begingroup$ Let $H=(V,E)$ where $|V|\ge5$ and $E=[V]^3$. Plainly $\chi(H)=\left\lceil\frac{|V|}2\right\rceil\ge3$. If $S\subseteq V$ and $|S\cap e|\le2$ for all $e\in E$ then $|S|\le2$ and $\chi(\operatorname{Gr}_H(S))\le2\lt\chi(H)$. Are you sure you stated the question correctly? $\endgroup$
    – bof
    Commented May 19, 2021 at 23:50
  • $\begingroup$ Thanks @bof - I have to think more about my formulation, but you can post this as an answer so we can close this thread as long as I don't have a better formulation $\endgroup$
    – Dominic van der Zypen
    Commented May 20, 2021 at 8:35
  • 2
    $\begingroup$ Maybe you could just delete this question, at least for now, and undelete it later if you come up with a corrected formulation? $\endgroup$
    – bof
    Commented May 20, 2021 at 8:49

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .