( 2 ​ k + 1 ) (2k+1) -Neighborhood Balanced Coloring

Maurice Genevieva Almeida · 2025

Read ( 2 ​ k + 1 ) (2k+1) -Neighborhood Balanced Coloring by Maurice Genevieva Almeida (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07758.txt.

Introduction

Maurice Genevieva Almeida studies balanced colorings of graphs where every vertex sees each color equally among its neighbors. His 2025 paper sets the number of colors to an odd prime count, written as 2k+1. Each vertex of a graph gets one of those colors. The coloring counts as balanced when, for every vertex, its neighbors split evenly across all colors. That is a strict demand on the graph's structure.

The paper establishes a range of results for common families of graphs. Some families are shown to admit such colorings. Others are presented with the property established case by case. The work sits in combinatorics, where parity and divisibility often decide what colorings can exist. By fixing the color count to a prime of a set form, the study links number theory with graph structure.

Catalog record

CREATORMaurice Genevieva Almeida
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-07758

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

( 2 ​ k + 1 ) (2k+1) -Neighborhood Balanced Coloring Maurice Genevieva Almeida Abstract Let G = ( V , E ) G=(V,E) be a simple graph and ( 2 ​ k + 1 ) (2k+1) be a prime integer. Let each vertex of G G be colored using one of the ( 2 ​ k + 1 ) (2k+1) colors, say R 1 , R 2 , … , R 2 ​ k + 1 R_{1},R_{2},...,R_{2k+1} . If every vertex has an equal number of neighbors of each color, then the coloring is a ( 2 ​ k + 1 ) (2k+1) -neighborhood balanced coloring. We establish a number of results for common families of graphs and present some families of graphs that have this property. 2020 Mathematics Subject Classification: 05C 78 Keywords: Vertex coloring, Neighborhood balanced coloring. 1 Introduction Let G=(V,E) be a simple graph. The order of G is |V| , and the size of G is |E| , and for any vertex v\in V , define the neighborhood of v as N(v)=\{u:uv\in E\} . The members of N(v) are the neighbors of v . For graph theoretic notations, we refer to Chartrand and Lesniak [ 1 ] . Freyberg et al. [ 2 ] introduced the concept of neighborhood balanced coloring as follows: Let G be a graph with each vertex colored one of two colors (e.g. red and blue). If every vertex has an equal number of neighbors of each color, then the coloring is a neighborhood balanced coloring (NBC). It is easy to see that if a graph admits a neighborhood balanced coloring, then the degree of every vertex is even. For such a coloring, let \sigma(BB) be the number of blue-blue edges, \sigma(RR) be the number of red-red edges, and let \sigma(RB) be the number of red-blue edges in a neighborhood balanced coloring \sigma of a graph. Similarly, let \sigma(B) and \sigma(R) denote the number of blue and red vertices, respectively, in a neighborhood balanced graph coloring \sigma . Freyberg et al. [ 2 ] proved the following results about graphs admitting neighborhood balanced coloring. Theorem 1.1 . [ 2 ] Suppose a graph G admits a neighborhood balanced coloring \sigma , then \sigma(RB)=\frac{|E(G)|}{2} and \sigma(RR)=\sigma(BB)=\frac{|E(G)|}{4} . Corollary 1.2 . [ 2 ] Suppose G is a regular graph on n vertices that admits a neighborhood balanced coloring \sigma . Then \sigma(R)=\sigma(B)=\frac{n}{2} . Corollary 1.3 . [ 2 ] If G is a regular graph on n vertices that admits a neighborhood balanced coloring, then n is even and |E(G)|\equiv 0\ (\bmod\ 4) . Freyberg et al. [ 2 ] studied the neighborhood balanced coloring of cycle C_{n} , the complete graph K_{n} , and the complete multipartite graph. They also studied the neighborhood balanced coloring of various graph products. Theorem 1.4 . [ 2 ] If graphs G and H admit neighborhood balanced colorings, then the lexicographic product G[H] admits a neighborhood balanced coloring. Theorem 1.5 . [ 2 ] Let G and H be graphs. If H admits a neighborhood balanced coloring with \sigma(R)=\sigma(B) , then the lexicographic product G[H] admits a neighborhood balanced coloring. Theorem 1.6 . [ 2 ] If G and H both admit neighborhood balanced colorings, then so does the cartesian product G\ \square\ H . Freyberg et al. [ 2 ] further completely classified 4-regular circulants that possess neighborhood balanced colorings. Theorem 1.7 . [ 2 ] A quartic circulant graph G\cong C_{n}(a,b) with gcd(n,a,b)=1 admits a neighborhood balanced coloring if and only if n is even, 1\leq a<b<\frac{n}{2} , and one of the following statements is true: 1. a\not\equiv b\ (mod\ 2) 2. a\equiv b\equiv 1\ (mod\ 2) and n\equiv 0\ (mod\ 4) . Taking motivation from this, we define a new concept called (2k+1) -neighborhood balanced coloring, for a prime integer (2k+1) , as follows: Definition 1.8 . Let G be a graph with each vertex colored with one of the (2k+1) colors, say R_{1},R_{2},R_{3},\dots,R_{2k+1} . If every vertex has an equal number of neighbors of each color, then the coloring is a (2k+1) -neighborhood balanced coloring. In other words, a (2k+1) -neighborhood balanced coloring is a partition of V into (2k+1) sets such that each vertex has an equal number of neighbors from each set. Sometimes it is convenient to use c\colon V\rightarrow\{-k,-(k-1),\dots,-1,0,1,\dots,,k-1,k\} to denote a (2k+1) -coloring with each number representing a different color. Let w(v)=\sum_{u\in N(v)}c(u) . Thus, G admits a (2k+1) -neighborhood balanced coloring if and only if w(v)=0 . Note that if h^{1} is a (2k+1) -neighborhood balanced coloring of graph G using colors in the order R_{1},R_{2},\dots,R_{2k+1} , then the colorings h^{2},h^{3},\dots,h^{2k+1} obtained by rotating the colors in a cyclic order are also (2k+1) -neighborhood balanced coloring of the graph G . In this paper, we present some characteristics of graphs that admit (2k+1) -neighborhood balanced coloring. We also study (2k+1) -neighborhood balanced coloring of various graph products. 2 Main Results The following proposition gives a necessary condition for a graph to admit a (2k+1) -neighborhood balanced coloring. Proposition 2.1 . If a graph G admits a (2k+1) -neighborhood balanced coloring, then the degree of every vertex is a multiple of (2k+1) . Let R_{1} , R_{2} , \dots , R_{2k+1} be the (2k+1) colors. Let \sigma(R_{i}R_{j}) be the number of R_{i}R_{j} edges and \sigma(R_{i}R_{i}) be the number of R_{i}R_{i} edges in a (2k+1) -neighborhood balanced coloring of a graph G . Similarly, let \sigma(R_{i}) be the number of R_{i} colored vertices. Theorem 2.2 . Suppose G has n vertices and admits a (2k+1) -neighborhood balanced coloring. Then for any (2k+1) -neighborhood balanced coloring \sigma , \sigma(R_{i}R_{j})=\frac{2|E(G)|}{(2k+1)^{2}}\ \text{and}\ \sigma(R_{i}R_{i})=\frac{|E(G)|}{(2k+1)^{2}}. Proof. Let \mathcal{R}_{i} stand for the set of R_{i} colored vertices, in a coloring of V . Consider the bipartite subgraph H of G induced by the set of R_{i}R_{j} edges. Then for any v\in\mathcal{R}_{i}\cup\mathcal{R}_{j}, d_{H}(v)=\frac{1}{2k+1}d_{G}(v). Therefore, counting \sigma(R_{i}R_{j}) by summing degrees over each part of the bipartite graph, \sigma(R_{i}R_{j})=\sum_{v\in\mathcal{R}_{i}}\frac{1}{2k+1}d_{G}(v)=\sum_{v\in\mathcal{R}_{j}}\frac{1}{2k+1}d_{G}(v) (1) which implies \sum_{v\in\mathcal{R}_{i}}d_{G}(v)=\sum_{v\in\mathcal{R}_{j}}d_{G}(v). Thus, \displaystyle 2|E(G)| \displaystyle=\sum_{v\in\mathcal{R}_{1}}d_{G}(v)+\sum_{v\in\mathcal{R}_{2}}d_{G}(v)+\dots+\sum_{v\in\mathcal{R}_{2k+1}}d_{G}(v) \displaystyle=(2k+1)\sum_{v\in\mathcal{R}_{i}}d_{G}(v) \displaystyle=(2k+1)^{2}\sigma(R_{i}R_{j}) which proves the first claim of the theorem. As for the second assertion, let G_{{R}_{i}} be the subgraph induced by the R_{i}R_{i} edges. For all v\in G_{R_{i}} , d_{G_{R_{i}}}(v)=\frac{1}{2k+1}d_{G}(v) . Therefore, by ( 1 ) and the first claim of the theorem, \displaystyle 2\sigma(R_{i}R_{i}) \displaystyle=\sum_{v\in G_{R_{i}}}d_{G_{R_{i}}}(v)=\sum_{v\in\mathcal{R}_{i}}\frac{1}{2k+1}d_{G}(v)=\sigma(R_{i}R_{j}) \displaystyle=\frac{2|E(G)|}{(2k+1)^{2}} Therefore \sigma(R_{i}R_{j})=\frac{|E(G)|}{(2k+1)^{2}}. ∎ Corollary 2.3 . Suppose G is a regular graph on n vertices of degree r>0 that admits a (2k+1) -neighborhood balanced coloring. Then \sigma(R_{i})=\dfrac{n}{2k+1}. Proof. From ( 1 ) we have, \displaystyle\sigma(R_{i}R_{j}) \displaystyle=\frac{1}{2k+1}\sum_{v\in\mathcal{R}_{i}}d_{G}(v)=\frac{r\sigma(R_{i})}{2k+1} \displaystyle=\frac{1}{2k+1}\sum_{v\in\mathcal{R}_{j}}d_{G}(v)=\frac{r\sigma(R_{j})}{2k+1} which implies \sigma(R_{i})=\sigma(R_{j}). As \sigma(R_{1})+\sigma(R_{2})+\dots+\sigma(R_{2k+1})=n , we have \sigma(R_{i})=\dfrac{n}{2k+1}. ∎ Corollary 2.4 . If G is a regular graph on n vertices of degree r>0 that admits a (2k+1) -neighborhood balanced coloring, then n\equiv 0\bmod(2k+1) and |E(G)|=0\bmod(2k+1)^{2} . Proof. Corollary 2.3 gives n is a multiple of (2k+1) and |E(G)|=(2k+1)^{2}\sigma(R_{i}R_{j}) from Theorem 2.2 . ∎ Theorem 2.5 . The complete graph K_{n} admits a (2k+1) -neighborhood balanced coloring if and only if n=1 . Proof. If n=1 , any coloring is (2k+1) -neighborhood balanced coloring. So assume n\geq 2 . Suppose a (2k+1) -neighborhood balanced coloring exists. Since K_{n} is a regular graph of degree n-1 , by Preposition 2.1 , n-1 is a

Read the complete text