Counting edge-injective homomorphisms and matchings on restricted graph classes

Counting edge-injective homomorphisms and matchings on restricted graph classes

他のバージョン（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...

書誌詳細
主要な著者:	Curticapean, R, Dell, H, Roth, M
フォーマット:	Journal article
言語:	English
出版事項:	Springer Nature 2018

類似資料

Counting edge-injective homomorphisms and matchings on restricted graph classes
著者:: Curticapean, R, 等
出版事項: (2017)

Parameterized counting of partially injective homomorphisms
著者:: Roth, M
出版事項: (2021)

Counting, modular counting and graph homomorphisms
著者:: Magkakis, A
出版事項: (2016)

Counting restricted homomorphisms via Möbius inversion over matroid lattices
著者:: Roth, M
出版事項: (2017)

Counting homomorphisms to K4-minor-free graphs, modulo 2
著者:: Focke, J, 等
出版事項: (2021)

Counting homomorphisms to K4-minor-free graphs, modulo 2
著者:: Focke, J, 等
出版事項: (2021)

Counting Homomorphisms to Square-Free Graphs, Modulo 2
著者:: Gobel, A, 等
出版事項: (2015)

The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
著者:: Göbel, A, 等
出版事項: (2013)

Counting homomorphisms to square-free graphs, modulo 2
著者:: Goldberg, L, 等
出版事項: (2016)

Homomorphic and restricted homomorphic products of softgraphs
著者:: Jinta Jose, 等
出版事項: (2025-01-01)

Counting and finding homomorphisms is universal for parameterized complexity theory
著者:: Roth, M, 等
出版事項: (2020)

ON HOMOMORPHISM GRAPHS
著者:: Sebastian Brandt, 等
出版事項: (2024-01-01)

The undecidability of joint embedding and joint homomorphism for hereditary graph classes
著者:: Samuel Braunfeld
出版事項: (2019-12-01)

The complexity of counting surjective homomorphisms and compactions
著者:: Focke, J, 等
出版事項: (2017)

The complexity of counting surjective homomorphisms and compactions
著者:: Focke, J, 等
出版事項: (2019)

Graph homomorphisms for quantum players
著者:: Mančinska, Laura, 等
出版事項: (2018)

Homomorphisms and related contractions of graphs
著者:: Robert D. Girse, 等
出版事項: (1988-01-01)

Homomorphically Full Oriented Graphs
著者:: Thomas Bellitto, 等
出版事項: (2023-10-01)

Graph homomorphisms between trees
著者:: Csikvari, Peter, 等
出版事項: (2015)

Retractions and Homomorphisms on Some Operations of Graphs
著者:: M. Abu-Saleem
出版事項: (2018-01-01)

On the complexity of counting homomorphisms under surjectivity constraints
著者:: Focke, J
出版事項: (2020)

On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
著者:: Christopher Duffy, 等
出版事項: (2021-03-01)

Graph homomorphisms via vector colorings
著者:: Godsil, Chris, 等
出版事項: (2020)

Homomorphisms of complete n-partite graphs
著者:: Robert D. Girse
出版事項: (1986-01-01)

Entropy, Graph Homomorphisms, and Dissociation Sets
著者:: Ziyuan Wang, 等
出版事項: (2023-01-01)

The Bipartite Swapping Trick on Graph Homomorphisms
著者:: Zhao, Yufei
出版事項: (2011)

Homomorphism and Isomorphism of Neutrosophic Over Topologized Graphs
著者:: G. Muthumari, 等
出版事項: (2023-01-01)

Complexity of locally-injective homomorphisms to tournaments
著者:: Stefan Bard, 等
出版事項: (2018-11-01)

The Restricted Edge-Connectivity of Strong Product Graphs
著者:: Hazhe Ye, 等
出版事項: (2024-03-01)

Polynomials Counting Nowhere-Zero Chains Associated with Homomorphisms
著者:: Martin Kochol
出版事項: (2024-10-01)

A Value for Graph-Restricted Games with Middlemen on Edges
著者:: Antonio C. Alarcón, 等
出版事項: (2022-05-01)

Classes of graphs with restricted interval models
著者:: Andrzej Proskurowski, 等
出版事項: (1999-01-01)

Classes of graphs with restricted interval models
著者:: Andrzej Proskurowski, 等
出版事項: (1999-12-01)

On 3-Restricted Edge Connectivity of Replacement Product Graphs
著者:: Yilan Cui, 等
出版事項: (2023-05-01)

Injective edge coloring of generalized Petersen graphs
著者:: Yanyi Li, 等
出版事項: (2021-05-01)

A dichotomy for homomorphism−closed queries on probabilistic graphs
著者:: Amarilli, A, 等
出版事項: (2020)

Undecidability of polynomial inequalities in weighted graph homomorphism densities
著者:: Grigoriy Blekherman, 等
出版事項: (2024-01-01)

The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
著者:: Antoine Amarilli, 等
出版事項: (2022-01-01)

Homomorphisms of planar signed graphs to signed projective cubes
著者:: Reza Naserasr, 等
出版事項: (2013-09-01)

On an edge partition and root graphs of some classes of line graphs
著者:: K Pravas, 等
出版事項: (2017-04-01)