On core of categorical product of (di)graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912370843975680 |
|---|---|
| author | Naserasr, Reza Pujol, Cyril |
| author_facet | Naserasr, Reza Pujol, Cyril |
| contents | The core of a graph is the smallest graph (in terms of number of vertices) to which it is homomorphically equivalent.
The question of the possible order of the core of the tensor product (also known as categorical, Heidetnemi or direct product) of two graphs captures some well known problems. For instance, the recent counterexample to the Hedetniemi conjecture for 5-chromatic graphs is equivalent to saying that there are cores of order at least 5 whose product has a core of order 4.
In this work, motivated by a question from Leonid Libkin in the area of graph databases, we first present methods of building cores whose categorical product is also a core. Extending on this we present sufficient conditions for a set of cores to have a product which is also a core. Presenting an example of such a family of digraphs, we construct a family of $\binom{2n}{n}$ digraphs, where the number of vertices of each is between $n^2+5n+2$ and $3n^2+3n+2$ and the product is a core. We then present a method of transforming the example into a family of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On core of categorical product of (di)graphs Naserasr, Reza Pujol, Cyril Combinatorics Discrete Mathematics The core of a graph is the smallest graph (in terms of number of vertices) to which it is homomorphically equivalent. The question of the possible order of the core of the tensor product (also known as categorical, Heidetnemi or direct product) of two graphs captures some well known problems. For instance, the recent counterexample to the Hedetniemi conjecture for 5-chromatic graphs is equivalent to saying that there are cores of order at least 5 whose product has a core of order 4. In this work, motivated by a question from Leonid Libkin in the area of graph databases, we first present methods of building cores whose categorical product is also a core. Extending on this we present sufficient conditions for a set of cores to have a product which is also a core. Presenting an example of such a family of digraphs, we construct a family of $\binom{2n}{n}$ digraphs, where the number of vertices of each is between $n^2+5n+2$ and $3n^2+3n+2$ and the product is a core. We then present a method of transforming the example into a family of graphs. |
| title | On core of categorical product of (di)graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2505.07463 |