Core

Core --- ядро.

1. Given a graph [math]\displaystyle{ G }[/math], a core of [math]\displaystyle{ G }[/math] is a subgraph [math]\displaystyle{ C }[/math] of [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ G }[/math] is homomorphic to [math]\displaystyle{ C }[/math], but [math]\displaystyle{ C }[/math] fails to be homomorphic to any proper subgraph of [math]\displaystyle{ G }[/math]. This notion of a core is due to Hell and Ne\u{s}et\u{r}il (1992). A graph [math]\displaystyle{ G }[/math] is a core if [math]\displaystyle{ G }[/math] is a core for itself. It is known, that in general, the problem of deciding whether [math]\displaystyle{ G }[/math] is a core is NP-complete, but there exists a polinomial time algorithm to decide if [math]\displaystyle{ G }[/math] is a core for the particular case when [math]\displaystyle{ G }[/math] has the independence number [math]\displaystyle{ \alpha(G) \leq 2 }[/math]. Finally, it is known that "almost all graphs" are cores.

2. Let [math]\displaystyle{ \Omega(G) }[/math] denote the family of all maximum stable sets. Then the core is defined as [math]\displaystyle{ core(G) = \cap \{S: \; S \in \Omega(G)\} }[/math]. Thus, the core is the set of vertices belonging to all maximum stable sets.