Skip to main content
3 of 3
fixed definition
domotorp
  • 18.9k
  • 3
  • 57
  • 127

Chromatic number of 2-graph vs hypergraph of point-line incidences

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.

domotorp
  • 18.9k
  • 3
  • 57
  • 127