Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Contact graphs of bo ...
Article

Contact graphs of boxes with unidirectional contacts

Daniel Gonçalves, Vincent Limouzy, Pascal Ochem
Download article
Open on arXiv
Submitted on
January 13, 2023
Accepted on
October 19, 2023
Published on
May 17, 2024
Last modified on
March 27, 2025
Special issue 25
vol. 25:3 special issue ICGT'22
Special issues
DOI
10.46298/dmtcs.10805
License
arXiv.org - Non-exclusive license to distribute
Algorithmics of metric covering problems in graphs
Indicators
894
Views
854
Downloads

Contact graphs of boxes with unidirectional contacts

Daniel Gonçalves, Vincent Limouzy, Pascal Ochem
Abstract
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
Keywords
  • Computer Science - Discrete Mathematics
  • Mathematics - Combinatorics
Mathematics Subject Classification 2020
  • 05C62 - Graph representations (geometric and intersection representations, etc.)
  • 05C76 - Graph operations (line graphs, products, etc.)
Preview
Loading PDF preview...