Back to Search Start Over

Coloring curves that cross a fixed curve

Authors :
Alexandre Rok
Bartosz Walczak
Publication Year :
2019

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.<br />Comment: Small corrections, improved presentation

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....f519ca60df1a6fbae060543342a83b00