LOCALLY-BALANCED $k$-PARTITIONS OF GRAPHS

Authors

  • Aram H. Gharibyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
  • Petros A. Petrosyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2021.55.2.096

Keywords:

$2$-partition, $k$-partition, locally-balanced $k$-partition, complete graph, biregular bipartite graph

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.

Downloads

Published

2021-08-30

How to Cite

Gharibyan, A. H., & Petrosyan, P. A. (2021). LOCALLY-BALANCED $k$-PARTITIONS OF GRAPHS. Proceedings of the YSU A: Physical and Mathematical Sciences, 55(2 (255), 96–112. https://doi.org/10.46991/PYSU:A/2021.55.2.096

Issue

Section

Mathematics