Cover Image

The complexity of frugal digraph homomorphisms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bard, Stefan, MacGillivray, Gary, Swarts, Jacobus
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Computational Complexity 05C15
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A dichotomy theorem for $Γ$-switchable $H$-colouring on $m$-edge coloured graphs
by: Brewster, Richard, et al.
Published: (2023)

Hamiltonicity of Bell and Stirling Colour Graphs
by: Finbow, Stephen, et al.
Published: (2025)

Colourings of $(m, n)$-coloured mixed graphs
by: MacGillivray, Gary, et al.
Published: (2020)

Bounding the Eviction Number of a Graph in Terms of its Independence Number
by: MacGillivray, Gary, et al.
Published: (2025)

Homomorphically Full Oriented Graphs
by: Bellitto, Thomas, et al.
Published: (2022)

The complexity of matroid homomorphism reconfiguration
by: Heo, Cheolwon, et al.
Published: (2025)

Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs
by: Jaworska, Justyna, et al.
Published: (2025)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

On complexity of substructure connectivity and restricted connectivity of graphs
by: Lü, Huazhong, et al.
Published: (2021)

On the complexity of Sandwich Problems for $M$-partitions
by: Barsukov, Alexey, et al.
Published: (2026)

The dib-chromatic number of digraphs
by: Javier-Nol, Nahid, et al.
Published: (2024)

Cut covers of acyclic digraphs
by: Krone, Maximilian
Published: (2024)

On the dib-chromatic number of a digraph
by: Montellano-Ballesteros, Juan José, et al.
Published: (2025)

Maximising homomorphism counts between digraphs
by: Lüchtrath, Lukas, et al.
Published: (2026)

Discreteness of asymptotic tensor ranks
by: Briët, Jop, et al.
Published: (2023)

The Gamma-Switch Ramsey Number
by: Duffy, Christopher, et al.
Published: (2026)

Zykov sums of digraphs with diachromatic number equal to their harmonious number
by: Olsen, Mika, et al.
Published: (2022)

Distinguishing symmetric digraphs by proper arc-colourings of type I
by: Kalinowski, Rafał, et al.
Published: (2025)

An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence
by: Wang, Kai
Published: (2026)

Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors
by: Olsen, Mika, et al.
Published: (2025)

On distinguishing digraphs by its quasisymmetric B-polynomial
by: Narayanan, N., et al.
Published: (2022)

Kernels in digraphs with colored vertices
by: Guevara, Mucuy-kak, et al.
Published: (2025)

Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
by: Fujii, Soichiro, et al.
Published: (2024)

Deriving differential approximation results for $k\,$CSPs from combinatorial designs
by: Culus, Jean-François, et al.
Published: (2024)

On the singularity and the inverse of 3-colored digraphs
by: Zaffer, Md Isheteyak
Published: (2026)

Quantum Advantage and CSP Complexity
by: Ciardo, Lorenzo
Published: (2024)

Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)

On the Quantum Chromatic Gap
by: Ciardo, Lorenzo
Published: (2025)

Classical Simulation of Quantum CSP Strategies
by: Banakh, Demian, et al.
Published: (2025)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
by: Ciardo, Lorenzo, et al.
Published: (2025)

On coloring graphs with well-distributed edge density
by: Hassan, Syed Mujtaba, et al.
Published: (2024)

Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free
by: Fujii, Soichiro, et al.
Published: (2024)

Algorithmic counting of nonequivalent compact Huffman codes
by: Elsholtz, Christian, et al.
Published: (2019)

Clique-Width: Harnessing the Power of Atoms
by: Dabrowski, Konrad K., et al.
Published: (2020)

Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]
by: Dourado, Mitre C., et al.
Published: (2023)

Abstract questionnaires and FS-decision digraphs
by: Chen, Jiaye, et al.
Published: (2025)

On the Complexity of Bipartite Degree Realizability
by: Miklós, István
Published: (2025)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs
by: Bousquet, Nicolas, et al.
Published: (2025)

On the interval coloring impropriety of graphs
by: Carr, MacKenzie, et al.
Published: (2023)