Skip to main content
fixed definition
Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 126

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

By what function of $\chi(G)$$\chi(G(P))$ can we bound $\chi(H)$$\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.

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.

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.

added 13 characters in body
Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 126

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.

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, $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.

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.

Source Link
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, $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.