Disjointness graphs of segments

DOI10.4230/LIPICS.SOCG.2017.59zbMATH Open1432.68365arXiv1704.01892MaRDI QIDQ4580137FDOQ4580137

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

Publication date: 13 August 2018

Abstract: The {em disjointness graph} $G=G(calS)$ of a set of segments $calS$ in $R^d$, $dge2,$ is a graph whose vertex set is $calS$ 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)le(omega(G){)}^4+(omega(G){)}^3$, where $omega(G)$ denotes the clique number of $G$. It follows, that $calS$ has $Omega(n^{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.

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

Recommendations

• Disjointness graphs of segments in the space
• The chromatic number of the convex segment disjointness graph
• On the chromatic number of disjointness graphs of curves
• The Chromatic Number of the Disjointness Graph of the Double Chain
• On the connectivity of the disjointness graph of segments of point sets in general position in the plane

zbMATH Keywords

\(\chi\)-boundedchromatic numberclique numberdisjointness graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (15)

• Disjointness graphs of short polygonal chains
• Hasse diagrams with large chromatic number
• Disjointness graphs of segments in \(\mathbb{R}^2\) are almost all Hamiltonian
• The maximum chromatic number of the disjointness graph of segments on \(n\)-point sets in the plane with \(n\leq 16\)
• Title not available (Why is that?)
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• The chromatic number of the convex segment disjointness graph
• Coloring lines and Delaunay graphs with respect to boxes
• On the chromatic number of disjointness graphs of curves
• Disjointness graphs of segments in the space
• Disjointness graphs of short polygonal chains
• Disjoint edges in geometric graphs
• Disjoint edges in geometric graphs
• Coloring Hasse diagrams and disjointness graphs of curves
• On the connectivity of the disjointness graph of segments of point sets in general position in the plane

This page was built for publication: Disjointness graphs of segments

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