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