Neighborhood Balanced k-Coloring of Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914026570645504 |
|---|---|
| author | Almeida, Maurice Genevieva Singh, Tarkeshwar Gupta, Siddharth Pawar, Ravindra |
| author_facet | Almeida, Maurice Genevieva Singh, Tarkeshwar Gupta, Siddharth Pawar, Ravindra |
| contents | For a simple graph G = (V, E) and a positive integer k greater than or equal to 2, a coloring of vertices of G using exactly k colors such that each vertex has an equal number of neighbors of each color is called neighborhood-balanced k-coloring, and the graph is called a neighborhood-balanced 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-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 NP-complete. Furthermore, we prove that there is no forbidden subgraph characterization for the class of neighborhood-balanced k-colorable graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06003 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Neighborhood Balanced k-Coloring of Graphs Almeida, Maurice Genevieva Singh, Tarkeshwar Gupta, Siddharth Pawar, Ravindra Combinatorics 05C 78 For a simple graph G = (V, E) and a positive integer k greater than or equal to 2, a coloring of vertices of G using exactly k colors such that each vertex has an equal number of neighbors of each color is called neighborhood-balanced k-coloring, and the graph is called a neighborhood-balanced 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-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 NP-complete. Furthermore, we prove that there is no forbidden subgraph characterization for the class of neighborhood-balanced k-colorable graphs. |
| title | Neighborhood Balanced k-Coloring of Graphs |
| topic | Combinatorics 05C 78 |
| url | https://arxiv.org/abs/2509.06003 |