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.

    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
    • 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 191 times.
    This article's PDF has been downloaded 108 times.