The core of a graph
type: Item
instance of: scholarly article
title: The core of a graph
zbMATH Open document ID: 0803.68080
DOI: 10.1016/0012-365X(92)90282-K
author: Pavol Hell
author: J. Nešetřil
published in: Discrete Mathematics
publication date: 1993-10-14T00:00:00Z
review text: Let \(H= (V(H),E(H))\) and \(G= (V(G),E(G))\) be graphs which may be either directed or undirected but always finite. A homomorphism \(G\to H\) is a mapping \(f: V(G)\to V(H)\) such that \(gg'\in E(G)\) implies \(f(g)f(g')\in E(H)\). If \(H\) is a subgraph of \(G\) then a homomorphism \(G\to H\) such that \(f(h)= h\) for all \(h\in V(H)\) is called a retraction of \(G\) onto \(H\), and \(H\) a retract of \(G\). A subgraph \(H\) of \(G\) is called a core of \(G\) if there is a homomorphism \(G\to H\), but no homomorphism \(G\to H'\) for any proper subgraph \(H'\) of \(H\). It is easy to show that every finite graph has a core and that the core is unique. Furthermore, the core of a graph is its smallest retract. The main result of this paper is a proof that the problem of deciding whether a graph \(G\) is its own core is \({\mathcal N}{\mathcal P}\)-complete. It is also shown that it is \({\mathcal N}{\mathcal P}\)- complete to decide whether or not a graph is rigid, i.e., admits only the identity homomorphism to itself. Finally, the authors show that if the independence number of \(G\) is two, then problem of deciding whether \(G\) is a core becomes polynomially solvable, and they pose the problem of investigating the complexity of the core problem for graphs with independence number three.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 428130
zbMATH Keywords: homomorphisms
zbMATH Keywords: retracts of graph
zbMATH Keywords: cores
zbMATH Keywords: NP-completeness
zbMATH Keywords: \(H\)-colouring
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: On minimal graphs
cites work: Q4049082
cites work: Q5659578
cites work: Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees)
cites work: Cohomomorphisms of graphs and hypergraphs
cites work: On the complexity of H-coloring
cites work: Unretractive and S-unretractive joins and lexicographic products of graphs
cites work: Endomorphisms of graphs. II: Various unretractive graphs
cites work: Chromatically optimal rigid graphs
cites work: Fixed-edge theorem for graphs with loops
cites work: Matching theory
cites work: Minimum node covers and 2-bicritical graphs
cites work: Q3208855
cites work: Color-families are dense
full work available at URL: 0012-365x(92)90282-k
OpenAlex ID: W2073279331
Recommended article: Q4863448
Recommended article: Q3139534
Recommended article: Q5471356
Recommended article: Cores of geometric graphs
Recommended article: Q4387747
Recommended article: On the core of a unicyclic graph
Recommended article: Center of a graph with respect to edges
Recommended article: The absolute centre of a graph
Recommended article: Cores and shells of graphs
Recommended article: Cores of cubelike graphs
description: scientific article; zbMATH DE number 428130