Neighborhood Balanced k k -Coloring of Graphs
2025
Read Neighborhood Balanced k k -Coloring of Graphs (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-2509-06003.txt.
Introduction
Coloring a graph so every vertex sees its neighbors' colors in perfect balance is the puzzle of a 2025 paper led by Maurice Genevieva Almeida with three co-authors. A neighborhood-balanced k-coloring uses exactly k colors, and each vertex must have equally many neighbors of each color. The notion generalizes an earlier two-color concept from the literature.
The authors derive necessary and sufficient conditions for such colorings and sort out which graph classes admit them. Deciding whether a given graph has one turns out to be NP-complete, so no fast general test is expected. They also prove no forbidden-subgraph characterization exists for the colorable class, closing a natural classification route.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06003
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Neighborhood Balanced k k -Coloring of Graphs Abstract For a simple graph G = ( V , E ) G=(V,E) and a positive integer k ≥ 2 k\geq 2 , a coloring of vertices of G G using exactly k k colors such that each vertex has an equal number of neighbors of each color is called neighborhood-balanced k k -coloring , and the graph is called neighborhood-balanced k k -colored graph. This generalizes the notion of neighborhood balanced coloring of graphs introduced by Bryan Freyberg and Alison Marr (Graphs and Combinatorics, 2024). We derive some necessary/sufficient conditions for a graph to admit a neighborhood-balanced k k -coloring and discuss several graph classes that admit such colorings. We also show that the problem of determining whether a given graph has such a coloring is 𝖭𝖯 \mathsf{NP} -complete. Furthermore, we prove that there is no forbidden subgraph characterization for the class of neighborhood-balanced k k -colorable graphs. 2020 Mathematics Subject Classification: 05C 78 Keywords: graph coloring, neighborhood-balanced k -coloring, \mathsf{NP} -completeness. 1 Introduction Let G=(V,E) be a simple graph. For any vertex v\in V , define the neighborhood of v as a set N(v):=\{u:uv\in E\} . The members of N(v) are called the neighbors of v and the cardinality of N(v) is called the degree of v , denoted as d(v) . Further, if we add the vertex v to its neighborhood N(v) , then we get the closed neighborhood of v , denoted by N[v] . For graph-theoretic notation, we refer to Chartrand and Lesniak [ 3 ] . Freyberg et al. [ 6 ] introduced the concept ‘neighborhood balanced coloring’. A neighborhood balanced coloring of a graph G is a vertex coloring of G using two colors, say red and green, such that each vertex has an equal number of neighbors of both colors. It is easy to see that if a graph admits a neighborhood balanced coloring, then the degree of every vertex is even. This notion of coloring is somewhat similar to cordial labeling [ 2 ] . In [ 6 ] , the authors characterized the 2 -regular graphs, complete graphs, and complete multipartite graphs that are colorable in a neighborhood balanced manner. In addition, they showed that in a neighborhood balanced colored graph G , the number of red-green edges is half the number of edges of G , and the number of red-red or green-green edges is one-fourth the number of edges of G . Minyard et al. [ 7 ] introduced the concept of ‘neighborhood balanced 3 -coloring’ of a graph and gave a characterization of several classes of graphs that admit such a coloring. A graph is said to admit a neighborhood balanced 3 -coloring if the vertices of G can be colored using exactly three colors such that each vertex has an equal number of neighbors of all three colors. In this article, we study similar coloring using k colors, called ‘neighborhood-balanced k -coloring’ of graphs, for any positive integer k\geq 2 . This generalizes the existing notions of neighborhood balanced coloring and neighborhood balanced 3 -coloring. Formally, a neighborhood-balanced k -coloring of a graph is defined as follows. Definition 1.1 . Let G be a graph, and let k\geq 2 be an integer. If the vertices of G can be colored using the k colors, say 1,2,\dots,k , so that every vertex has an equal number of neighbors of each color, then the coloring is an neighborhood-balanced k -coloring of G . A graph that admits such a coloring is called a neighborhood-balanced k -colorable graph. In other words, a neighborhood-balanced k -coloring of graph G is a partition of the vertex set V of G into k sets V_{1},V_{2},\dots,V_{k} (that is, color classes) such that every vertex has an equal number of neighbors in each set. Sometimes it is convenient to use c\colon V\rightarrow\{-k,\dots,0,\dots,k\} to denote a (2k+1) -coloring and c\colon V\rightarrow\{-k,\dots,-1,1,\dots,k\} to denote a 2k -coloring. Let w(v)=\sum_{u\in N(v)}c(u) . Thus, G admits a neighborhood-balanced k -coloring if and only if w(v)=0 for all v\in V(G) . Note that if c is a neighborhood-balanced k -coloring of graph G using colors in the order (1,2,\dots,k) , then the colorings c=c_{1},c_{2},\dots,c_{k} obtained by rotating the colors in a cyclic order are also neighborhood-balanced k -colorings of G . We refer to such colorings as the colorings obtained by cyclic shift of c . Definition 1.2 (Equally colored set) . Let c be a vertex coloring of a graph G . A subset X\subseteq V(G) is said to be equally colored if each color appears the same number of times in X . An equally colored set X is called a rainbow if each color appears in X exactly once. Now we can restate the definition of neighborhood-balanced k -coloring graph as: a graph G is neighborhood-balanced k -colored if a set N(v) is equally colored for all vertices v\in V(G) . Similarly, we call a graph G closed neighborhood-balanced k -colored if N[v] is equally colored for every vertex v\in V(G) . This concept is already introduced and studied for k=2 in [ 5 ] . A neighborhood-balanced k -colored can also describe settings in need of a combination of two or more complementary abilities or perspectives. For instance, imagine a learning environment of a team learning where each student is allocated one of three roles: Analyst (red), Communicator (blue), or Innovator (green). Draw the students as vertices, and join the vertices by an edge if the respective students tend to work together. A neighborhood balanced 3 -coloring implies that within each student’s immediate social circle of students, each of the three roles is represented in a balanced way. This organization facilitates overall learning by introducing each student to analytical, communicative, and creative aspects through their day-to-day interactions. In Section 2 , we prove some necessary conditions for a graph to admit a neighborhood-balanced k -coloring and we characterize some graph classes that admit such a coloring. Further, we prove that there is no forbidden subgraph characterization for the class of neighborhood-balanced k -colorable graphs. In Section 3 , we prove that the decision problem ‘Given a graph G and a positive integer k\geq 2 , does G admit a neighborhood-balanced k -coloring?’ is \mathsf{NP} -complete. Figure 1 : A neighborhood-balanced 2 -coloring of C_{8} . 2 Main Results We begin this section by deriving some necessary conditions for graphs to admit a neighborhood-balanced k -coloring. Note that if a graph admits such a coloring, then its minimum degree is k . We state this necessary condition in the following lemma in a more general form. Lemma 2.1 . If a graph G admits a neighborhood-balanced k -coloring, then the degree of every vertex is a multiple of k . Observe that a neighborhood-balanced k -colored graph without isolated vertices cannot have exactly one vertex of any color. Lemma 2.2 . If G is a neighborhood-balanced k -colored graph without isolated vertices, then the order of G is at least 2k . The lower bound on the order of a neighborhood-balanced k -colored graph given in the above lemma is sharp. There are neighborhood-balanced k -colored graphs of order