Locally-balanced $k$-partitions of graphs

В работе обобщены локально-сбалансированные $2$-разбиения графов и введено новое понятие – локально сбалансированные $k$-разбиения графов, определяемые следующим образом: сюръекция $f:V(G)\rightarrow \{0,1,...,k-1\}$ называется $k$-разбиением графа $G$. $k$-Разбиение ($k \geq 2$) $f$ графа $G$ является локально-сбалансированным с открытой окрестностью, если для любой вершины $v \in V(G)$ и любых $ 0 \leq i <j \leq k-1$
$$\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=i\}\vert - \vert \{u\in N_{G}(v)\colon\,f(u)=j\}\vert \right\vert\leq 1.$$
$k$-Разбиение ($k \geq 2$) $f^{\prime}$ графа $G$ является локально-сбалансированным с закрытой окрестностью, если для любой вершины $v \in V(G)$ и любых $ 0 \leq i <j \leq k-1$
$$\left\vert \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=i\}\vert - \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=j\}\vert \right\vert\leq 1.$$
Mинимальное число $k$ ($ k \geq 2$), для которого граф $G$ имеет локально-сбалансированное $k$-разбиение с открытой (закрытой) окрестностью, называется $lb$-открытым ($lb$-закрытым) хроматическим числом $G$ и обозначается через $\chi_{(lb)}(G)$ ($\chi_{[lb]}(G)$). В работе даны оценки или определены точные значения $lb$-открытого и $lb$-закрытого хроматических чисел некоторых классов графов. Кроме того, рассмотрены связи $lb$-открытых и $lb$-закрытых хроматических чисел графов с другими хроматическими числами, такими как инъективные и $2$-дистанционные хроматические числа.