|
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.
Received: 25.02.2021 Revised: 18.05.2021 Accepted: 01.06.2021
Citation:
A. H. Gharibyan, P. A. Petrosyan, “Locally-balanced $k$-partitions of graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 55:2 (2021), 96–112
Linking options:
https://www.mathnet.ru/eng/uzeru837 https://www.mathnet.ru/eng/uzeru/v55/i2/p96
|
|