Skip to main content
2 of 3
added 13 characters in body
domotorp
  • 18.8k
  • 3
  • 57
  • 126

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 collection of points and lines in the plane, $P$ and $L$, consider the hypergraph $H(P,L)$ on the vertex set $P$ such that the edges are formed by the collinear points.
Define the graph $G(P,L)$ as the restriction of $H(P,L)$ to its edges of size 2.

By what function of $\chi(G)$ can we bound $\chi(H)$ 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.8k
  • 3
  • 57
  • 126