The Chromatic Number of the Disjointness Graph of the Double Chain
Let $P$ be a set of $n\geq 4$ points in general position in the plane. Consider all the closed straight line segments with both endpoints in $P$. Suppose that these segments are colored with the rule that disjoint segments receive different colors. In this paper we show that if $P$ is the point conf...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4490/pdf |
| Summary: | Let $P$ be a set of $n\geq 4$ points in general position in the plane.
Consider all the closed straight line segments with both endpoints in $P$.
Suppose that these segments are colored with the rule that disjoint segments
receive different colors. In this paper we show that if $P$ is the point
configuration known as the double chain, with $k$ points in the upper convex
chain and $l \ge k$ points in the lower convex chain, then $k+l- \left\lfloor
\sqrt{2l+\frac{1}{4}} - \frac{1}{2}\right\rfloor$ colors are needed and that
this number is sufficient. |
|---|---|
| ISSN: | 1365-8050 |