Abstract: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.
| Subjects: | Combinatorics (math.CO); Computational Complexity (cs.CC) |
| MSC classes: | 05C15 |
| Cite as: | arXiv:2605.24258 [math.CO] |
| (or arXiv:2605.24258v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24258 arXiv-issued DOI via DataCite (pending registration) |
From: Gary MacGillivray [view email]
[v1]
Fri, 22 May 2026 22:21:00 UTC (35 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。