The core of a graph

DOI10.1016/0012-365X(92)90282-KzbMath0803.68080OpenAlexW2073279331MaRDI QIDQ686290

Publication date: 14 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90282-k

zbMATH Keywords

homomorphisms NP-completeness cores \(H\)-colouring retracts of graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items

Triangle-free graphs and forbidden subgraphs, On the data complexity of consistent query answering, Removal lemmas and approximate homomorphisms, Graph homomorphisms with infinite targets, The complexity of restricted graph homomorphisms, Minimal universal and dense minor closed classes, Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings, Conjunctive query evaluation by search-tree revisited, Homomorphically full graphs, Dualities and dual pairs in Heyting algebras, Complexity of tree homomorphisms, Preserving Constraints with the Stable Chase, Covers of Query Results, Bare canonicity of representable cylindric and polyadic algebras, A More General Theory of Static Approximations for Conjunctive Queries, Solutions and query rewriting in data exchange, On the equivalence of distributed systems with queries and communication, The smallest hard trees, Graph homomorphisms via vector colorings, Minimum degree and the graph removal lemma, Security Protocol Analysis in Context: Computing Minimal Executions Using SMT and CPSA, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Arboreal categories and equi-resource homomorphism preservation theorems, Enumerating homomorphisms, Generalized K-Core Percolation in Networks with Community Structure, A generalization of the Łoś-Tarski preservation theorem, Robust Factorizations and Colorings of Tensor Graphs, Homomorphisms between graphs embedded in surfaces, On the homomorphism order of labeled posets, Colouring, constraint satisfaction, and complexity, The complexity of equivalence, entailment, and minimization in existential positive logic, FREE ADEQUATE SEMIGROUPS, Path homomorphisms, On retracts, absolute retracts, and foldings in cographs, Shifts of the stable Kneser graphs and hom-idempotence, On the complexity of existential positive queries, Foundations of semantic web databases, Data exchange: semantics and query answering, Unnamed Item, CoReS: a tool for computing core graphs via SAT/SMT solvers, RESIDUAL PROPERTIES OF SIMPLE GRAPHS, Testing subgraphs in directed graphs, Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation, A homotopy category for graphs, Maximal infinite-valued constraint languages, Testing the Complexity of a Valued CSP Language, Gibbs measures and dismantlable graphs, How many variables are needed to express an existential positive query?, HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results, A more general theory of static approximations for conjunctive queries, Generalized symmetry of graphs - a survey, A surprising permanence of old motivations (a not-so-rigid story), Chromatic numbers and products, Schema Mappings: A Case of Logical Dynamics in Database Theory, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Unnamed Item, Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree, Counting \(H-\)colorings of partial \(k-\)trees, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Convex-round graphs are circular-perfect

Cites Work