Cover Image

On a Hierarchy of Spectral Invariants for Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arvind, V., Fuhlbrück, Frank, Köbler, Johannes, Verbitsky, Oleg
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

Gathering Information about a Graph by Counting Walks from a Single Vertex
by: Fuhlbrück, Frank, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

Hierarchies of Minion Tests for PCSPs through Tensors
by: Ciardo, Lorenzo, et al.
Published: (2022)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

Lions and Contamination: Trees and General Graphs
by: Kim, Dohoon, et al.
Published: (2026)

On the Structure of Hamiltonian Graphs with Small Independence Number
by: Jedličková, Nikola, et al.
Published: (2024)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Graph Irregularity via Edge Deletions
by: Bensmail, Julien, et al.
Published: (2025)

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Computational Aspects of Cores of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

Finding a HIST: Chordality, Structural Parameters, and Diameter
by: Hanaka, Tesshu, et al.
Published: (2025)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Hardness of 4-Colourings G-Colourable Graphs
by: Avvakumov, Sergey, et al.
Published: (2025)

Finding d-Cuts in Claw-free Graphs
by: Ahn, Jungho, et al.
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
by: Concha-Vega, Pablo
Published: (2026)

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

Algorithmic methods of finite discrete structures. Graph clique problem
by: Kurapov, Sergey, et al.
Published: (2024)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
by: Dikstein, Yotam, et al.
Published: (2023)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)