О путевых ядрах и разбиениях в неориентированных графах

Пусть $\tau(G)$ обозначает число вершин в длиннейшем пути неориентированного графа $G$. Для пары натуральных чисел $(a,b)$ таких, что $a+b=\tau(G)$, граф $G$ называется $(a,b)$-разбиваемым, если его множество вершин $V(G)$ можно разбить на два класса $A$, $B$ таким образом, что $\tau(G[A])\leq a$ и $\tau(G[B])\leq b$, где $G[A]$ и $G[B]$ – индуцированные подграфы на множествах вершин $A$ и $B$ в $G$. Подмножество $K$ множества $V(G)$ называется $P_n$-ядром, если $\tau(G[K])\leq n-1$ и каждая вершина $v\in V(G-K)$ смежна с вершиной, которая является конечной в пути длины $n-1$ в графе $G$. Известно, что наличие $P_n$-ядра в графе $G$ означает, что $G$ является $(\tau(G)-n+1,n-1)$-разбиваемым. В настоящей статье доказано, что каждый граф имеет $P_8$-ядро.
Ил. 11, библиогр. 13.