Coloring curves intersecting a fixed line
Alexandre Rok, Bartosz Walczak · arXiv (Cornell University) · 2015
Let $\mathcal{F}$ be a family of curves in the plane with the following properties: (1) each member of $\mathcal{F}$ intersects a fixed straight line $L$ in at least one and at most $t$ points, (2) any two members of $\mathcal{F}$ intersect in at most one point, (3) the intersection graph of $\mathcal{F}$ is triangle-free. We prove that the chromatic number $\chi(\mathcal{F})$ of the intersection graph of $\mathcal{F}$ is bounded by a function of $t$. Dependence on $t$ is crucial. It follows easily from the existence of triangle-free segment intersection graphs with arbitrarily large chromatic number that $\chi(\mathcal{F})$ can be arbitrarily large as $t$ grows. It has been conjectured that the intersection graphs of families of curves $\mathcal{F}$ satisfying just condition 1 have chromatic number bounded in terms of $t$ and the clique number, which would generalize the recent result that the class of outerstring graphs is $\chi$-bounded. We also show that it is enough to establish the case $t=2$ in order to prove the conjecture for any $t$.