Geodesic
The Chromatic Number of the Disjointness Graph of the Double Chain
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.23638/DMTCS-22-1-11
Classification : 05C15 
@article{DMTCS_2020_22_1_a9,
     author = {Fabila-Monroy, Ruy and Hidalgo-Toscano, Carlos and Lea\~nos, Jes\'us and Lomel{\'\i}-Haro, Mario},
     title = {The {Chromatic} {Number} of the {Disjointness} {Graph} of the {Double} {Chain}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-11/}
}
TY  - JOUR
AU  - Fabila-Monroy, Ruy
AU  - Hidalgo-Toscano, Carlos
AU  - Leaños, Jesús
AU  - Lomelí-Haro, Mario
TI  - The Chromatic Number of the Disjointness Graph of the Double Chain
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-11/
DO  - 10.23638/DMTCS-22-1-11
LA  - en
ID  - DMTCS_2020_22_1_a9
ER  - 
%0 Journal Article
%A Fabila-Monroy, Ruy
%A Hidalgo-Toscano, Carlos
%A Leaños, Jesús
%A Lomelí-Haro, Mario
%T The Chromatic Number of the Disjointness Graph of the Double Chain
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-11/
%R 10.23638/DMTCS-22-1-11
%G en
%F DMTCS_2020_22_1_a9
Fabila-Monroy, Ruy; Hidalgo-Toscano, Carlos; Leaños, Jesús; Lomelí-Haro, Mario. The Chromatic Number of the Disjointness Graph of the Double Chain. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-11

Cité par Sources :