Coloring Curves that Cross a Fixed Curve
Alexandre Rok, Bartosz Walczak · Discrete & Computational Geometry · 2018
We prove that for every integer $$t\geqslant 1$$ , the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is $$\chi $$ -bounded. This is essentially the strongest $$\chi $$ -boundedness result one can get for those kind of graph classes. As a corollary, we prove that for any fixed integers $$k\geqslant 2$$ and $$t\geqslant 1$$ , every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has $$O(n\log n)$$ edges.