Simple view

Full metadata view

Authors

Statistics

The -binding function of -Directional segment graphs

2025
journal article
article
10.1007/s00454-025-00737-2
Journal
Discrete and Computational Geometry
100
Author
Duraj Lech

Kang Ross J.

La Xuân

Narboni Jonathan

Pokrývka Filip
Show more
Volume
74
Number
3
Pages
758-770
ISSN
0179-5376
eISSN
1432-0444
Keywords in English

geometric graphs

chi-boundedness

segment graphs

graph colouring

URL
https://link.springer.com/article/10.1007/s00454-025-00737-2
Access date
2025-12-19
Language
English
Journal language
English
Abstract in English

Given a positive integer , the class -DIR is defined as all those intersection graphs formed from a finite collection of line segments in having at most d slopes. Since each slope induces an interval graph, it easily follows for every in -DIR with clique number at most that the chromatic numer of is at most . We show for every even value of how to construct a graph in -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 -DIR is for even and for odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case .

Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.abstract.enGiven a positive integer $\textit{d}$, the class $\textit{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 $\textit{G}$ in $\textit{d}$-DIR with clique number at most $\omega$ that the chromatic numer $\chi\left(\textit{G}\right)$ of $\textit{G}$ is at most $\textit{d}\omega$. We show for every even value of $\omega$ how to construct a graph in $\textit{d}$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $\chi$-binding function of $\textit{d}$-DIR is $\omega\mapsto\mathit{d}\omega$ for $\omega$ even and $\omega\mapsto\textit{d}\left(\omega-1\right)+1$ for $\omega$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $\textit{d}=2$.
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorDuraj, Lech - 133967
dc.contributor.authorKang, Ross J.
dc.contributor.authorLa, Xuân - 474785
dc.contributor.authorNarboni, Jonathan - 477530
dc.contributor.authorPokrývka, Filip
dc.contributor.authorRambaud, Clément
dc.contributor.authorReinald, Amadeus
dc.date.accession2025-12-19
dc.date.accessioned2025-12-19T06:40:09Z
dc.date.available2025-12-19T06:40:09Z
dc.date.createdat2025-12-17T08:09:28Zen
dc.date.issued2025
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number3
dc.description.physical758-770
dc.description.versionostateczna wersja wydawcy
dc.description.volume74
dc.identifier.doi10.1007/s00454-025-00737-2
dc.identifier.eissn1432-0444
dc.identifier.issn0179-5376
dc.identifier.projectDRC AI
dc.identifier.urihttps://ruj.uj.edu.pl/handle/item/567920
dc.identifier.weblinkhttps://link.springer.com/article/10.1007/s00454-025-00737-2
dc.languageeng
dc.language.containereng
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.typeinne
dc.subject.engeometric graphs
dc.subject.enchi-boundedness
dc.subject.ensegment graphs
dc.subject.engraph colouring
dc.subtypeArticle
dc.titleThe $\chi$-binding function of $\textit{d}$-Directional segment graphs
dc.title.journalDiscrete and Computational Geometry
dc.typeJournalArticle
dspace.entity.typePublicationen
dc.abstract.en
Given a positive integer $\textit{d}$, the class $\textit{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 $\textit{G}$ in $\textit{d}$-DIR with clique number at most $\omega$ that the chromatic numer $\chi\left(\textit{G}\right)$ of $\textit{G}$ is at most $\textit{d}\omega$. We show for every even value of $\omega$ how to construct a graph in $\textit{d}$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $\chi$-binding function of $\textit{d}$-DIR is $\omega\mapsto\mathit{d}\omega$ for $\omega$ even and $\omega\mapsto\textit{d}\left(\omega-1\right)+1$ for $\omega$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $\textit{d}=2$.
dc.affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.author
Duraj, Lech - 133967
dc.contributor.author
Kang, Ross J.
dc.contributor.author
La, Xuân - 474785
dc.contributor.author
Narboni, Jonathan - 477530
dc.contributor.author
Pokrývka, Filip
dc.contributor.author
Rambaud, Clément
dc.contributor.author
Reinald, Amadeus
dc.date.accession
2025-12-19
dc.date.accessioned
2025-12-19T06:40:09Z
dc.date.available
2025-12-19T06:40:09Z
dc.date.createdaten
2025-12-17T08:09:28Z
dc.date.issued
2025
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.number
3
dc.description.physical
758-770
dc.description.version
ostateczna wersja wydawcy
dc.description.volume
74
dc.identifier.doi
10.1007/s00454-025-00737-2
dc.identifier.eissn
1432-0444
dc.identifier.issn
0179-5376
dc.identifier.project
DRC AI
dc.identifier.uri
https://ruj.uj.edu.pl/handle/item/567920
dc.identifier.weblink
https://link.springer.com/article/10.1007/s00454-025-00737-2
dc.language
eng
dc.language.container
eng
dc.rights
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
inne
dc.subject.en
geometric graphs
dc.subject.en
chi-boundedness
dc.subject.en
segment graphs
dc.subject.en
graph colouring
dc.subtype
Article
dc.title
The $\chi$-binding function of $\textit{d}$-Directional segment graphs
dc.title.journal
Discrete and Computational Geometry
dc.type
JournalArticle
dspace.entity.typeen
Publication
Affiliations
Wydział Matematyki i Informatyki
Duraj, Lech
computer and information sciences
La, Xuân
computer and information sciences
Narboni, Jonathan
computer and information sciences
No affiliation
Kang, Ross J.
Pokrývka, Filip
Rambaud, Clément
Reinald, Amadeus

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
12
Views per month
Views per city
Krakow
5

Open Access

Thumbnail Image
License
CC-BY

Except as otherwise noted, this item is licensed under : Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa

Collections
Research publications
DRC AI
Exact sciences