- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Disjointness Graphs
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Disjointness Graphs Pach, Janos
Description
The {\em disjointness graph} $G=G({\cal S})$ of a set of segments ${\cal S}$ in ${R}^d$, $d\ge 2,$ is a graph whose vertex set is ${\cal 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$ is bounded by a function of $\omega(G)$, the clique number of $G$. More precisely, we have $\chi(G)\le(\omega(G))^4+(\omega(G))^3$. It follows, that $\cal S$ 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-complete 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. Joint work with G\'abor Tardos and G\'eza T\'oth.
Item Metadata
Title |
Disjointness Graphs
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2017-05-23T13:30
|
Description |
The {\em disjointness graph} $G=G({\cal S})$ of a set of segments ${\cal S}$ in ${R}^d$, $d\ge 2,$ is a graph whose vertex set is ${\cal 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$ is bounded by a function of $\omega(G)$, the clique number of $G$. More precisely, we have $\chi(G)\le(\omega(G))^4+(\omega(G))^3$. It follows, that $\cal S$ 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-complete 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. Joint work with G\'abor Tardos and G\'eza T\'oth.
|
Extent |
34 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Ecole Polytechnique Federale de Lausanne
|
Series | |
Date Available |
2017-12-04
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0361151
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International