×

The core of a graph. (English) Zbl 0803.68080

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.

MSC:

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

References:

[1] Bang-Jensen, J.; Hell, P.; MacGillivray, G., On the complexity of colouring by tournaments and semicomplete digraphs, SIAM J. Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018
[2] Bang-Jensen, J.; Hell, P., The effect of two cycles on the complexity of colouring by directed graphs, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029
[3] Fellner, W. D., On minimal graphs, Theoret. Comput. Sci., 17, 103-110 (1982) · Zbl 0473.68063
[4] M. Fiklíová and J. Nešetřil, Density and homomorphisms, in preparation.; M. Fiklíová and J. Nešetřil, Density and homomorphisms, in preparation.
[5] Hell, P., Absolute retracts in graphs, (Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Math., Vol. 406 (1973), Springer: Springer Berlin), 291-301
[6] Hell, P.; Nešetřil, J., Rigid and inverse-rigid graphs, (Guy, R. K.; etal., Combinatorial Structures and their Applications (1970), Gordon and Breach: Gordon and Breach London), 169-171 · Zbl 0247.05137
[7] Hell, P.; Nešetřil, J., Groups and monoids of regular graphs (and of graphs with bounded degrees), Canad. J. Math., 25, 239-251 (1973) · Zbl 0253.05126
[8] Hell, P.; Nešetřil, J., Cohomomorphisms of graphs and hypergraphs, Math. Nachr., 87, 53-61 (1979) · Zbl 0435.05050
[9] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[10] Knauer, U., Unretractive and \(S\)-unretractive joins and lexicographic products of graphs, J. Graph Theory, 11, 429-440 (1987) · Zbl 0659.05055
[11] Knauer, U., Endomorphisms of graphs II., Various unretractive graphs, Arch. Math., 55, 193-203 (1990) · Zbl 0683.05027
[12] MacGillivray, G., Colouring by vertex-transitive diagraphs (1990), manuscript
[13] MacGillivray, G., Notes on restricted graph homomorphisms (1990), manuscript
[14] Nešetřil, J.; Pultr, A., On classes of relations and graphs defined by subobjects and factorobjects, Discrete Math., 22, 187-200 (1979)
[15] Nešetřil, J.; Rödl, V., Chromatically optimal rigid graphs, J. Combin. Theory Ser. B, 46, 133-141 (1989) · Zbl 0677.05031
[16] Nowakowski, R.; Rival, I., Fixed-edge theorem for graphs with loops, J. Graph Theory, 3, 339-350 (1979) · Zbl 0432.05030
[17] Lovász, L.; Plummer, M., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[18] Pulleyblank, W. R., Minimum node covers and 2-bicritical graphs, Math. Programming, 17, 92-103 (1979) · Zbl 0414.90066
[19] Pultr, A.; Trnková, V., Combinatorial, Algebraic and Topological Representations of Groups, (Semigroups and Categories (1980), North-Holland: North-Holland Amsterdam) · Zbl 0418.18004
[20] Welzl, E., Color-families are dense, Theoret. Comput. Sci., 17, 29-41 (1982) · Zbl 0482.68063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.