pith. sign in

arxiv: 1512.06112 · v5 · pith:RFPYNK77new · submitted 2015-12-18 · 🧮 math.CO · cs.CG· cs.DM

Coloring curves that cross a fixed curve

classification 🧮 math.CO cs.CGcs.DM
keywords fixedcurvecurvesedgeseverygraphprovebounded
0
0 comments X
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.