Quasi Neighborhood Balanced Coloring of Graphs

2025

Read Quasi Neighborhood Balanced 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-2512-24293.txt.

Description

Maurice Genevieva Almeida defines a new graph coloring. Vertices receive red or blue. The coloring is quasi neighborhood balanced when every vertex sees nearly equal colors around it. Red and blue neighbor counts may differ by at most one. At least one vertex must hit a difference of exactly one. Variants refine the idea further.

Uniform, positive, and negative variants depend on the extra neighbor's color. Only vertices of odd degree have such an extra neighbor. The paper gives examples of graph classes admitting each variant. Graph operations on such colored graphs are discussed. Two structural results close the study. No forbidden subgraph characterization exists for the class. Deciding whether a graph admits such a coloring is NP-complete. The notion joins the family of balanced coloring problems in graph theory.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-24293

Browse the full library · About the Tower of Babel