Coloring curves that cross a fixed curve

DOI10.4230/LIPICS.SOCG.2017.56MaRDI QIDQ4580134zbMATH OpenOpenAlexFDO

Authors Alexandre Rok, Bartosz Walczak

Publication date 13 August 2018

Full work available at URL https://arxiv.org/abs/1512.06112

zbMATH Keywords

\(\chi\)-boundednessstring graphs\(k\)-quasi-planar graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We prove that for every integer $tgeq1$, 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 $kgeq2$ and $tgeq1$, every $k$-quasi-planar topological graph on $n$ vertices with any two edges crossing at most $t$ times has $O(nlogn)$ edges.

Recommendations

• Coloring curves that cross a fixed curve
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• On the chromatic number of disjointness graphs of curves

Cited in

(7)

• Conflict-free coloring of string graphs
• Coloring curves that cross a fixed curve
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• On the chromatic number of disjointness graphs of curves
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Outerstring graphs are \(\chi\)-bounded
• Coloring intersection graphs of \(x\)-monotone curves in the plane

This page was built for publication: Coloring curves that cross a fixed curve

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580134)