Daniel Gonçalves ; Vincent Limouzy ; Pascal Ochem - Contact graphs of boxes with unidirectional contacts

dmtcs:10805 - Discrete Mathematics & Theoretical Computer Science, May 17, 2024, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10805
Contact graphs of boxes with unidirectional contactsArticle

Authors: Daniel Gonçalves ; Vincent Limouzy ; Pascal Ochem

This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free. We give several structural properties of these graphs, and we raise several questions.

Comment: Minor change

https://doi.org/10.46298/dmtcs.10805
Source: arXiv.org:2301.03865
Volume: vol. 25:3 special issue ICGT'22
Section: Special issues
Published on: May 17, 2024
Accepted on: October 19, 2023
Submitted on: January 13, 2023
Keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Licence: arXiv.org - Non-exclusive license to distribute
Funding:
    Source : OpenAIRE Graph
  • Graphs, Algorithms and TOpology; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0009
  • Algorithmics of metric covering problems in graphs; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0004

Share and export

Consultation statistics

This page has been seen 703 times.
This article's PDF has been downloaded 531 times.