Двудольно-пороговые графы

Тройка $(x, v, y)$ различных вершин графа $G = (V, E)$ такая, что $xv\in E$ и $vy\notin E$ называется повышающей, если $\mathrm{deg}(x)\leq \mathrm{deg}(y)$, и понижающей, если $\mathrm{deg}(x)\geq 2 + \mathrm{deg}(y)$. Преобразование $\varphi$ графа $G$ такое, что $\varphi(G) = G - xv + vy$, называется вращением ребра в графе $G$ вокруг вершины $v$, отвечающим тройке $(x, v, y)$. Вращение ребра в графе $G$, отвечающее тройке $(x, v, y)$, называется повышающим, если тройка $(x, v, y)$ повышающая, и понижающим, если тройка $(x, v, y)$ понижающая. Вращение $\varphi$ ребра в графе $G$ является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе $\varphi(G)$ является понижающим. Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. В работе найдены различные свойства, характеризующие двудольно-пороговые графы. В частности, каждый такой граф $(V_1, E, V_2)$ является подграфом порогового графа $(K(V_1), E, V_2)$, где $K(V_1)$ — полный граф на множестве вершин $V_1$. Отметим, что граф является пороговым тогда и только тогда, когда он не имеет повышающих троек вершин. Любой двудольный граф может быть получен из двудольно-порогового графа с помощью понижающих вращений ребер. С помощью полученных результатов и критерия Кохнерта графичности разбиения мы приводим новое достаточно простое доказательство известной теоремы Гейла и Райзера о представлении двух разбиений степенными разбиениями долей двудольного графа.