Ruy Fabila-Monroy ; Carlos Hidalgo-Toscano ; Jesús Leaños ; Mario Lomelí-Haro - The Chromatic Number of the Disjointness Graph of the Double Chain

dmtcs:4490 - Discrete Mathematics & Theoretical Computer Science, March 22, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-11
The Chromatic Number of the Disjointness Graph of the Double ChainArticle

Authors: Ruy Fabila-Monroy ; Carlos Hidalgo-Toscano ; Jesús Leaños ; Mario Lomelí-Haro

    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.


    Volume: vol. 22 no. 1
    Section: Graph Theory
    Published on: March 22, 2020
    Accepted on: February 13, 2020
    Submitted on: May 9, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1143 times.
    This article's PDF has been downloaded 583 times.