The complexity of frugal digraph homomorphisms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911710870241280 |
|---|---|
| author | Bard, Stefan MacGillivray, Gary Swarts, Jacobus |
| author_facet | Bard, Stefan MacGillivray, Gary Swarts, Jacobus |
| contents | For an integer $t \geq 1$, a homomorphism of a digraph G to a digraph $H$ is $t$-frugal if no more than $t$ in-neighbours of any vertex of $G$ have the same image. There is a dichotomy theorem based on structural properties when $t=1$ and $H$ has a loop at each vertex, but there is unlikely to be such a theorem for general digraphs $H$. For $t \geq 2$ we describe a structural dichotomy theorem for $t$-frugal homomorphisms of general digraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24258 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The complexity of frugal digraph homomorphisms Bard, Stefan MacGillivray, Gary Swarts, Jacobus Combinatorics Computational Complexity 05C15 For an integer $t \geq 1$, a homomorphism of a digraph G to a digraph $H$ is $t$-frugal if no more than $t$ in-neighbours of any vertex of $G$ have the same image. There is a dichotomy theorem based on structural properties when $t=1$ and $H$ has a loop at each vertex, but there is unlikely to be such a theorem for general digraphs $H$. For $t \geq 2$ we describe a structural dichotomy theorem for $t$-frugal homomorphisms of general digraphs. |
| title | The complexity of frugal digraph homomorphisms |
| topic | Combinatorics Computational Complexity 05C15 |
| url | https://arxiv.org/abs/2605.24258 |