License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.59
URN: urn:nbn:de:0030-drops-71960
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7196/
Go to the corresponding LIPIcs Volume Portal

Pach, János ; Tardos, Gábor ; Tóth, Géza

Disjointness Graphs of Segments

pdf-format:
LIPIcs-SoCG-2017-59.pdf (0.4 MB)

Abstract

The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments.

We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

BibTeX - Entry

@InProceedings{pach_et_al:LIPIcs:2017:7196,
  author =	{J{\'a}nos Pach and G{\'a}bor Tardos and G{\'e}za T{\'o}th},
  title =	{{Disjointness Graphs of Segments}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7196},
  URN =		{urn:nbn:de:0030-drops-71960},
  doi =		{10.4230/LIPIcs.SoCG.2017.59},
  annote =	{Keywords: disjointness graph, chromatic number, clique number, chi-bounded}
}

Keywords: disjointness graph, chromatic number, clique number, chi-bounded
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI