The core of a graph

DOI10.1016/0012-365X(92)90282-KMaRDI QIDQ686290zbMATH OpenOpenAlexFDO

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

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

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

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.

Recommendations

Cites work

Cited in

(87)

This page was built for publication: The core of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686290)