Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2309.06072 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916601571311616 |
|---|---|
| author | Duraj, Lech Kang, Ross J. La, Hoang Narboni, Jonathan Pokrývka, Filip Rambaud, Clément Reinald, Amadeus |
| author_facet | Duraj, Lech Kang, Ross J. La, Hoang Narboni, Jonathan Pokrývka, Filip Rambaud, Clément Reinald, Amadeus |
| contents | Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $ω$ that the chromatic number $χ(G)$ of $G$ is at most $dω$. We show for every even value of $ω$ how to construct a graph in $d$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $χ$-binding function of $d$-DIR is $ω\mapsto dω$ for $ω$ even and $ω\mapsto d(ω-1)+1$ for $ω$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $d=2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_06072 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The $χ$-binding function of $d$-directional segment graphs Duraj, Lech Kang, Ross J. La, Hoang Narboni, Jonathan Pokrývka, Filip Rambaud, Clément Reinald, Amadeus Combinatorics Computational Geometry Discrete Mathematics 05C15, 05C62, 05C17 Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $ω$ that the chromatic number $χ(G)$ of $G$ is at most $dω$. We show for every even value of $ω$ how to construct a graph in $d$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $χ$-binding function of $d$-DIR is $ω\mapsto dω$ for $ω$ even and $ω\mapsto d(ω-1)+1$ for $ω$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $d=2$. |
| title | The $χ$-binding function of $d$-directional segment graphs |
| topic | Combinatorics Computational Geometry Discrete Mathematics 05C15, 05C62, 05C17 |
| url | https://arxiv.org/abs/2309.06072 |