3
$\begingroup$

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ is not constant (that is, the vertices of every edge are colored with at least $2$ colors).

So far, all the hypergraphs I have come across that are $\kappa$-chromatic for some cardinal $\kappa>2$, but not $2$-chromatic have $2$ distinct edges such that their intersection is a singleton.

Question. Does there exist a hypergraph $H=(V,E)$ that is $\kappa$-chromatic for some cardinal $\kappa>2$, but not $2$-chromatic, such that for all $e,f\in E$ we have $e\cap f = \emptyset$ or $|e\cap f| > 1$?

$\endgroup$
  • 2
    $\begingroup$ It seems to me that the problem is interesting for integer valued chromatic numbers and maybe all the discussion about cardinals only obscures things (although I may be mistaken). I've been trying to come up with a non-2-colourable hypergraph which forbids intersections of size 1, but I've failed miserably! It seems like it might be a nice problem. $\endgroup$ – Jon Noel Jul 11 '17 at 21:33
  • $\begingroup$ @JonNoel You should stop trying (see below). See you in Waterloo soon. =) $\endgroup$ – Tony Huynh Jul 14 '17 at 13:53
  • $\begingroup$ Ah nice proof; I don't know how I missed that! Yes, see you soon! $\endgroup$ – Jon Noel Jul 14 '17 at 14:03
3
$\begingroup$

To answer Jon Noel's question in the comments, there is no such example for finite hypergraphs.

Claim. Let $H=(V,E)$ be a finite hypergraph such that $|e| > 1$ for all $e \in E$ and for all distinct $e_1, e_2 \in E$, $|e_1 \cap e_2| \neq 1$. Then $H$ is $2$-chromatic.

Proof. We proceed by induction on $|E|$. The base case is clear. Now arbitrarily choose $e \in E$ and let $G=(V, E \setminus e)$. By induction, $G$ has a $2$-coloring $c$. If two vertices in $e$ receive distinct colors from $c$, then $c$ is a $2$-colouring of $H$ and we are done. So we may assume that all vertices in $e$ are red. We now choose a vertex $x \in e$ and recolor $x$ blue. This is a valid $2$-colouring of $H$ unless there is an edge $f \in E$ such that $x \in f$ and all other vertices in $f$ are blue. But this implies that $|e \cap f|=1$, which is a contradiction.

$\endgroup$
  • 3
    $\begingroup$ This is Problem 13.33 in Lovasz's book: Combinatorial problems and exercises. He does not give reference, but I think it came from Erdos. $\endgroup$ – Péter Komjáth Jul 14 '17 at 6:00
0
$\begingroup$

There is an infinite example. Let ${\cal U}$ be a free ultrafilter on $\omega$, then $H=(\omega,{\cal U})$ is not $2$-colorable by Coloring non-principal ultrafilters on $\omega$ and no intersection of 2 edges is a singleton.

$\endgroup$

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.