Pach, János ;
Tomon, István
On the Chromatic Number of Disjointness Graphs of Curves
Abstract
Let omega(G) and chi(G) denote the clique number and chromatic number of a graph G, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called xmonotone if every vertical line intersects it in at most one point. An xmonotone curve is grounded if its left endpoint lies on the yaxis.
We prove that if G is the disjointness graph of a family of grounded xmonotone curves such that omega(G)=k, then chi(G)<= binom{k+1}{2}. If we only require that every curve is xmonotone and intersects the yaxis, then we have chi(G)<= k+1/2 binom{k+2}{3}. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist K_kfree disjointness graphs of xmonotone curves such that any proper coloring of them uses at least Omega(k^{4}) colors. This matches the upper bound up to a constant factor.
BibTeX  Entry
@InProceedings{pach_et_al:LIPIcs:2019:10458,
author = {J{\'a}nos Pach and Istv{\'a}n Tomon},
title = {{On the Chromatic Number of Disjointness Graphs of Curves}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {54:154:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10458},
URN = {urn:nbn:de:0030drops104582},
doi = {10.4230/LIPIcs.SoCG.2019.54},
annote = {Keywords: string graph, chromatic number, intersection graph}
}
11.06.2019
Keywords: 

string graph, chromatic number, intersection graph 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

11.06.2019 