Coloring curves that cross a fixed curve

DOI10.4230/LIPICS.SOCG.2017.56zbMATH Open1432.05069arXiv1512.06112OpenAlexW2902518546MaRDI QIDQ4580134FDOQ4580134

Authors: Alexandre Rok, Bartosz Walczak 

Publication date: 13 August 2018

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.

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

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

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)

Cited In (7)

• Conflict-free coloring of string graphs
• Coloring curves that cross a fixed curve
• Title not available (Why is that?)
• On the chromatic number of disjointness graphs of curves
• Outerstring graphs are \(\chi\)-bounded
• Coloring k _k -free intersection graphs of geometric objects in the plane
• 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)