Counting edge-injective homomorphisms and matchings on restricted graph classes

Counting edge-injective homomorphisms and matchings on restricted graph classes

Show other versions (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...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Curticapean, R, Dell, H, Roth, M
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	Springer Nature 2018

Eitemau Tebyg

Counting edge-injective homomorphisms and matchings on restricted graph classes
gan: Curticapean, R, et al.
Cyhoeddwyd: (2017)

Parameterized counting of partially injective homomorphisms
gan: Roth, M
Cyhoeddwyd: (2021)

Counting, modular counting and graph homomorphisms
gan: Magkakis, A
Cyhoeddwyd: (2016)

Counting restricted homomorphisms via Möbius inversion over matroid lattices
gan: Roth, M
Cyhoeddwyd: (2017)

Counting homomorphisms to K4-minor-free graphs, modulo 2
gan: Focke, J, et al.
Cyhoeddwyd: (2021)

Counting homomorphisms to K4-minor-free graphs, modulo 2
gan: Focke, J, et al.
Cyhoeddwyd: (2021)

Counting Homomorphisms to Square-Free Graphs, Modulo 2
gan: Gobel, A, et al.
Cyhoeddwyd: (2015)

The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
gan: Göbel, A, et al.
Cyhoeddwyd: (2013)

Counting homomorphisms to square-free graphs, modulo 2
gan: Goldberg, L, et al.
Cyhoeddwyd: (2016)

Homomorphic and restricted homomorphic products of softgraphs
gan: Jinta Jose, et al.
Cyhoeddwyd: (2025-01-01)

Counting and finding homomorphisms is universal for parameterized complexity theory
gan: Roth, M, et al.
Cyhoeddwyd: (2020)

ON HOMOMORPHISM GRAPHS
gan: Sebastian Brandt, et al.
Cyhoeddwyd: (2024-01-01)

The undecidability of joint embedding and joint homomorphism for hereditary graph classes
gan: Samuel Braunfeld
Cyhoeddwyd: (2019-12-01)

The complexity of counting surjective homomorphisms and compactions
gan: Focke, J, et al.
Cyhoeddwyd: (2017)

The complexity of counting surjective homomorphisms and compactions
gan: Focke, J, et al.
Cyhoeddwyd: (2019)

Graph homomorphisms for quantum players
gan: Mančinska, Laura, et al.
Cyhoeddwyd: (2018)

Homomorphisms and related contractions of graphs
gan: Robert D. Girse, et al.
Cyhoeddwyd: (1988-01-01)

Homomorphically Full Oriented Graphs
gan: Thomas Bellitto, et al.
Cyhoeddwyd: (2023-10-01)

Graph homomorphisms between trees
gan: Csikvari, Peter, et al.
Cyhoeddwyd: (2015)

Retractions and Homomorphisms on Some Operations of Graphs
gan: M. Abu-Saleem
Cyhoeddwyd: (2018-01-01)

On the complexity of counting homomorphisms under surjectivity constraints
gan: Focke, J
Cyhoeddwyd: (2020)

On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
gan: Christopher Duffy, et al.
Cyhoeddwyd: (2021-03-01)

Graph homomorphisms via vector colorings
gan: Godsil, Chris, et al.
Cyhoeddwyd: (2020)

Homomorphisms of complete n-partite graphs
gan: Robert D. Girse
Cyhoeddwyd: (1986-01-01)

Entropy, Graph Homomorphisms, and Dissociation Sets
gan: Ziyuan Wang, et al.
Cyhoeddwyd: (2023-01-01)

The Bipartite Swapping Trick on Graph Homomorphisms
gan: Zhao, Yufei
Cyhoeddwyd: (2011)

Homomorphism and Isomorphism of Neutrosophic Over Topologized Graphs
gan: G. Muthumari, et al.
Cyhoeddwyd: (2023-01-01)

Complexity of locally-injective homomorphisms to tournaments
gan: Stefan Bard, et al.
Cyhoeddwyd: (2018-11-01)

The Restricted Edge-Connectivity of Strong Product Graphs
gan: Hazhe Ye, et al.
Cyhoeddwyd: (2024-03-01)

Polynomials Counting Nowhere-Zero Chains Associated with Homomorphisms
gan: Martin Kochol
Cyhoeddwyd: (2024-10-01)

A Value for Graph-Restricted Games with Middlemen on Edges
gan: Antonio C. Alarcón, et al.
Cyhoeddwyd: (2022-05-01)

Classes of graphs with restricted interval models
gan: Andrzej Proskurowski, et al.
Cyhoeddwyd: (1999-01-01)

Classes of graphs with restricted interval models
gan: Andrzej Proskurowski, et al.
Cyhoeddwyd: (1999-12-01)

On 3-Restricted Edge Connectivity of Replacement Product Graphs
gan: Yilan Cui, et al.
Cyhoeddwyd: (2023-05-01)

Injective edge coloring of generalized Petersen graphs
gan: Yanyi Li, et al.
Cyhoeddwyd: (2021-05-01)

A dichotomy for homomorphism−closed queries on probabilistic graphs
gan: Amarilli, A, et al.
Cyhoeddwyd: (2020)

Undecidability of polynomial inequalities in weighted graph homomorphism densities
gan: Grigoriy Blekherman, et al.
Cyhoeddwyd: (2024-01-01)

The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
gan: Antoine Amarilli, et al.
Cyhoeddwyd: (2022-01-01)

Homomorphisms of planar signed graphs to signed projective cubes
gan: Reza Naserasr, et al.
Cyhoeddwyd: (2013-09-01)

On an edge partition and root graphs of some classes of line graphs
gan: K Pravas, et al.
Cyhoeddwyd: (2017-04-01)