1
$\begingroup$

Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in the plane, consider the hypergraph $H(P)$ on the vertex set $P$ such that $E\subset P$ is a hyperedge if $|E|\ge 2$ and there is a line $\ell$ such that $\ell\cap P=E$.
Define the graph $G(P)$ as the restriction of $H(P)$ to its edges of size 2.

By what function of $\chi(G(P))$ can we bound $\chi(H(P))$ from above?

Note: The dual of this question was asked by a new and anonymous user 2 days ago, who shortly afterwards deleted it.

Improve this question
$\endgroup$
4
  • $\begingroup$ You mean, these are points and lines on the usual Euclidean plane? $\endgroup$
    – Fedor Petrov
    Commented Jan 25, 2023 at 15:34
  • $\begingroup$ I am confused. Is not it true that $\chi(H)\leqslant \chi(G)$ - of course, if all edges have at least two vertices - by using the same coloring? $\endgroup$
    – Fedor Petrov
    Commented Jan 25, 2023 at 17:58
  • $\begingroup$ or you mean that the edges of $H$ are not collinear sets, but only inclusion-maximal? $\endgroup$
    – Fedor Petrov
    Commented Jan 25, 2023 at 18:00
  • $\begingroup$ @Fedor I'm sorry, what I wrote first made little sense. I hope now it's ok. $\endgroup$
    – domotorp
    Commented Jan 25, 2023 at 20:43

0

Reset to default

You must log in to answer this question.