Imagen de Portada

The complexity of frugal digraph homomorphisms

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bard, Stefan, MacGillivray, Gary, Swarts, Jacobus
Formato:	Preprint
Publicado:	2026
Materias:	Combinatorics Computational Complexity 05C15
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

Homomorphically Full Oriented Graphs
por: Bellitto, Thomas, et al.
Publicado: (2022)

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

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

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

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

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

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

Cut covers of acyclic digraphs
por: Krone, Maximilian
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

Quantum Advantage and CSP Complexity
por: Ciardo, Lorenzo
Publicado: (2024)

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

On the Quantum Chromatic Gap
por: Ciardo, Lorenzo
Publicado: (2025)

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

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

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

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

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

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

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

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

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

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

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

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