RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, Physical and Mathematical Sciences, 2021 Volume 55, Issue 2, Pages 96–112 (Mi uzeru837)

Mathematics

Locally-balanced $k$-partitions of graphs

A. H. Gharibyan, P. A. Petrosyan

Yerevan State University, Faculty of Informatics and Applied Mathematics

Abstract: In this paper we generalize locally-balanced $2$-partitions of graphs and introduce a new notion, the locally-balanced $k$-partitions of graphs, defined as follows: a $k$-partition of a graph $G$ is a surjection $f:V(G)\rightarrow \{0,1,\ldots,k-1\}$. A $k$-partition ($k\geq 2$) $f$ of a graph $G$ is a locally-balanced with an open neighborhood, if for every $v\in V(G)$ and any $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.$$
A $k$-partition ($k\geq 2$) $f^{\prime}$ of a graph $G$ is a locally-balanced with a closed neighborhood, if for every $v\in V(G)$ and any $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.$$
The minimum number $k$ ($k\geq 2$), for which a graph $G$ has a locally-balanced $k$-partition with an open (a closed) neighborhood, is called an $lb$-open ($lb$-closed) chromatic number of $G$ and denoted by $\chi_{(lb)}(G)$ ($\chi_{[lb]}(G)$). In this paper we determine or bound the $lb$-open and $lb$-closed chromatic numbers of several families of graphs. We also consider the connections of $lb$-open and $lb$-closed chromatic numbers of graphs with other chromatic numbers such as injective and $2$-distance chromatic numbers.

MSC: 05C70; 05C15

Received: 25.02.2021
Revised: 18.05.2021
Accepted: 01.06.2021

Language: English

DOI: 10.46991/PYSU:A/2021.55.2.096



© Steklov Math. Inst. of RAS, 2025