DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2019.54

On the Chromatic Number of Disjointness Graphs of Curves

Authors: János Pach and István Tomon

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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 x-monotone if every vertical line intersects it in at most one point. An x-monotone curve is grounded if its left endpoint lies on the y-axis. We prove that if G is the disjointness graph of a family of grounded x-monotone curves such that omega(G)=k, then chi(G)<= binom{k+1}{2}. If we only require that every curve is x-monotone and intersects the y-axis, 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_k-free disjointness graphs of x-monotone 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.

Cite as

János Pach and István Tomon. On the Chromatic Number of Disjointness Graphs of Curves. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2019.54,
  author =	{Pach, J\'{a}nos and Tomon, Istv\'{a}n},
  title =	{{On the Chromatic Number of Disjointness Graphs of Curves}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.54},
  URN =		{urn:nbn:de:0030-drops-104582},
  doi =		{10.4230/LIPIcs.SoCG.2019.54},
  annote =	{Keywords: string graph, chromatic number, intersection graph}
}

Search Results

Documents authored by Tomon, István

On the Chromatic Number of Disjointness Graphs of Curves

Abstract

Cite as

Thanks for your feedback!

Could not send message