Coloring curves that cross a fixed curve
classification
🧮 math.CO
cs.CGcs.DM
keywords
fixedcurvecurvesedgeseverygraphprovebounded
read the original abstract
We prove that for every integer $t\geq 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 this kind of graph classes. As a corollary, we prove that for any fixed integers $k\geq 2$ and $t\geq 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.