The core of a graph

1992/11/01 by Pavol Hell, Jaroslav Nešetřil · 1 voice · 11 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation

paper · doi:10.1016/0012-365x(92)90282-k

crossref issued 1992/11/01 · crossref published 1992/11/01 · crossref published-print 1992/11/01 · openalex publication_date 1992/11/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/07/02 · openalex updated_date 2026/07/16

Cited by

• Containment, Equivalence and Coreness from CSP to QCSP and beyond
• Growth and identities of monogenic free adequate monoids
• Polynomial Property Testing
• The Logic of Counting Query Answers
• Kernelization for H-Coloring
• Parallel-Correctness and Transferability for Conjunctive Queries
• SHACL Validation in the Presence of Ontologies: Semantics and Rewriting Techniques
• Reopening of the conjecture about the decidability of Quasi-Dense Modal Logics (Comments on Lyon & Ostropolski-Nalewaja's result)
• Free adequate semigroups
• Laconic schema mappings: computing core universal solutions by means of SQL queries
• Data exchange: getting to the core

Discussions

• This is not known. If it were true, then all of NP would be in QuasiP, because testing whether a graph is a core is NP-complete: doi.org/10.1016/0012... [bsky, 2 points, 1 comments]