Contact graphs of boxes with unidirectional contacts

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 gr...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2024-05, Vol.25:3 special issue... (Special issues)
Main Authors: Gonçalves, Daniel, Limouzy, Vincent, Ochem, Pascal
Format: Article
Language:English
Subjects:
Computer Science
computer science - discrete mathematics
Discrete Mathematics
mathematics - combinatorics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.10805