P4-Связный граф

$P_{4}$-Связный граф ($P_{4}$-Connected graph) — граф $G = (V,E)$, у которого для каждого разбиения множества $V$ на непересекающиеся подмножества $V_{1}$ и $V_{2}$ найдется некоторая цепь без хорд с четырьмя вершинами и тремя ребрами (т.е. $P_{4}$), которая содержит вершины как из $V_{1}$, так и из $V_{2}$.

Различают следующие классы графов с простыми $P_{4}$-структурами: $P_{4}$-сводимые (reducible), $P_{4}$-растяжимые (extendible), $P_{4}$-разреженные (sparse).

Литература

• Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.