On constrained intersection representations of graphs and digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912346568392704 |
|---|---|
| author | Cicalese, Ferdinando Dallard, Clément Milanič, Martin |
| author_facet | Cicalese, Ferdinando Dallard, Clément Milanič, Martin |
| contents | We study the problem of determining optimal directed intersection representations of DAGs in a model introduced by Kostochka, Liu, Machado, and Milenkovic [ISIT2019]: vertices are assigned color sets so that there is an arc from a vertex $u$ to a vertex $v$ if and only if their color sets have nonempty intersection and $v$ gets assigned strictly more colors than $u$, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18365 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On constrained intersection representations of graphs and digraphs Cicalese, Ferdinando Dallard, Clément Milanič, Martin Discrete Mathematics Data Structures and Algorithms Information Theory Combinatorics We study the problem of determining optimal directed intersection representations of DAGs in a model introduced by Kostochka, Liu, Machado, and Milenkovic [ISIT2019]: vertices are assigned color sets so that there is an arc from a vertex $u$ to a vertex $v$ if and only if their color sets have nonempty intersection and $v$ gets assigned strictly more colors than $u$, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs. |
| title | On constrained intersection representations of graphs and digraphs |
| topic | Discrete Mathematics Data Structures and Algorithms Information Theory Combinatorics |
| url | https://arxiv.org/abs/2504.18365 |