Counting edge-injective homomorphisms and matchings on restricted graph classes

Counting edge-injective homomorphisms and matchings on restricted graph classes

Taispeáin leaganacha eile (1)

We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently vi...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Curticapean, R, Dell, H, Roth, M
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	Springer Nature 2018

Míreanna comhchosúla

Counting edge-injective homomorphisms and matchings on restricted graph classes
de réir: Curticapean, R, et al.
Foilsithe / Cruthaithe: (2017)

Parameterized counting of partially injective homomorphisms
de réir: Roth, M
Foilsithe / Cruthaithe: (2021)

Counting, modular counting and graph homomorphisms
de réir: Magkakis, A
Foilsithe / Cruthaithe: (2016)

Counting restricted homomorphisms via Möbius inversion over matroid lattices
de réir: Roth, M
Foilsithe / Cruthaithe: (2017)

Counting homomorphisms to K4-minor-free graphs, modulo 2
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Counting homomorphisms to K4-minor-free graphs, modulo 2
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Counting Homomorphisms to Square-Free Graphs, Modulo 2
de réir: Gobel, A, et al.
Foilsithe / Cruthaithe: (2015)

The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
de réir: Göbel, A, et al.
Foilsithe / Cruthaithe: (2013)

Counting homomorphisms to square-free graphs, modulo 2
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

Homomorphic and restricted homomorphic products of softgraphs
de réir: Jinta Jose, et al.
Foilsithe / Cruthaithe: (2025-01-01)

Counting and finding homomorphisms is universal for parameterized complexity theory
de réir: Roth, M, et al.
Foilsithe / Cruthaithe: (2020)

ON HOMOMORPHISM GRAPHS
de réir: Sebastian Brandt, et al.
Foilsithe / Cruthaithe: (2024-01-01)

The undecidability of joint embedding and joint homomorphism for hereditary graph classes
de réir: Samuel Braunfeld
Foilsithe / Cruthaithe: (2019-12-01)

The complexity of counting surjective homomorphisms and compactions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of counting surjective homomorphisms and compactions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2019)

Graph homomorphisms for quantum players
de réir: Mančinska, Laura, et al.
Foilsithe / Cruthaithe: (2018)

Homomorphisms and related contractions of graphs
de réir: Robert D. Girse, et al.
Foilsithe / Cruthaithe: (1988-01-01)

Homomorphically Full Oriented Graphs
de réir: Thomas Bellitto, et al.
Foilsithe / Cruthaithe: (2023-10-01)

Graph homomorphisms between trees
de réir: Csikvari, Peter, et al.
Foilsithe / Cruthaithe: (2015)

Retractions and Homomorphisms on Some Operations of Graphs
de réir: M. Abu-Saleem
Foilsithe / Cruthaithe: (2018-01-01)

On the complexity of counting homomorphisms under surjectivity constraints
de réir: Focke, J
Foilsithe / Cruthaithe: (2020)

On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
de réir: Christopher Duffy, et al.
Foilsithe / Cruthaithe: (2021-03-01)

Graph homomorphisms via vector colorings
de réir: Godsil, Chris, et al.
Foilsithe / Cruthaithe: (2020)

Homomorphisms of complete n-partite graphs
de réir: Robert D. Girse
Foilsithe / Cruthaithe: (1986-01-01)

Entropy, Graph Homomorphisms, and Dissociation Sets
de réir: Ziyuan Wang, et al.
Foilsithe / Cruthaithe: (2023-01-01)

The Bipartite Swapping Trick on Graph Homomorphisms
de réir: Zhao, Yufei
Foilsithe / Cruthaithe: (2011)

Homomorphism and Isomorphism of Neutrosophic Over Topologized Graphs
de réir: G. Muthumari, et al.
Foilsithe / Cruthaithe: (2023-01-01)

Complexity of locally-injective homomorphisms to tournaments
de réir: Stefan Bard, et al.
Foilsithe / Cruthaithe: (2018-11-01)

The Restricted Edge-Connectivity of Strong Product Graphs
de réir: Hazhe Ye, et al.
Foilsithe / Cruthaithe: (2024-03-01)

Polynomials Counting Nowhere-Zero Chains Associated with Homomorphisms
de réir: Martin Kochol
Foilsithe / Cruthaithe: (2024-10-01)

A Value for Graph-Restricted Games with Middlemen on Edges
de réir: Antonio C. Alarcón, et al.
Foilsithe / Cruthaithe: (2022-05-01)

Classes of graphs with restricted interval models
de réir: Andrzej Proskurowski, et al.
Foilsithe / Cruthaithe: (1999-01-01)

Classes of graphs with restricted interval models
de réir: Andrzej Proskurowski, et al.
Foilsithe / Cruthaithe: (1999-12-01)

On 3-Restricted Edge Connectivity of Replacement Product Graphs
de réir: Yilan Cui, et al.
Foilsithe / Cruthaithe: (2023-05-01)

Injective edge coloring of generalized Petersen graphs
de réir: Yanyi Li, et al.
Foilsithe / Cruthaithe: (2021-05-01)

A dichotomy for homomorphism−closed queries on probabilistic graphs
de réir: Amarilli, A, et al.
Foilsithe / Cruthaithe: (2020)

Undecidability of polynomial inequalities in weighted graph homomorphism densities
de réir: Grigoriy Blekherman, et al.
Foilsithe / Cruthaithe: (2024-01-01)

The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
de réir: Antoine Amarilli, et al.
Foilsithe / Cruthaithe: (2022-01-01)

Homomorphisms of planar signed graphs to signed projective cubes
de réir: Reza Naserasr, et al.
Foilsithe / Cruthaithe: (2013-09-01)

On an edge partition and root graphs of some classes of line graphs
de réir: K Pravas, et al.
Foilsithe / Cruthaithe: (2017-04-01)