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$
3
  • 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
    Commented Jul 11, 2017 at 21:33
  • $\begingroup$ @JonNoel You should stop trying (see below). See you in Waterloo soon. =) $\endgroup$
    – Tony Huynh
    Commented Jul 14, 2017 at 13:53
  • $\begingroup$ Ah nice proof; I don't know how I missed that! Yes, see you soon! $\endgroup$
    – Jon Noel
    Commented Jul 14, 2017 at 14:03

2 Answers 2

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$
1
  • 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$ Commented Jul 14, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .