Chromatic numbers with open and nonzero local modular constraints

2025/09/06 by Herden, Daniel, Meddaugh, Jonathan, Sepanski, Mark R. +9
#Combinatorics (math.CO) #FOS: Mathematics #Primary: 05C78 #Secondary: 05C25

paper · doi:10.48550/arxiv.2509.05822

Abstract

In this paper, we explore chromatic numbers subject to various local modular constraints. For fixed n, we consider proper integer colorings of a graph G for which the closed and open neighborhood sums have nonzero remainders modulo n and provide bounds for the associated chromatic numbers χ_n(G) and χ_(n)(G), respectively. In addition, we provide bounds for χ_(n,k)(G), the minimal order of a proper integer coloring of G with open neighborhood sums congruent to k\mod n (when such a coloring exists) as well as precise values for certain families of graphs.

Citations

• Chromatic numbers with closed local modular constraints
• Boundedness for proper conflict-free and odd colorings
• Remarks on odd colorings of graphs
• Colorings with neighborhood parity condition
• On the chromatic number in the stochastic block model
• Large cliques in graphs with high chromatic number

Related

• Chromatic numbers with closed local modular constraints
• On Modular Edge Colourings of Graphs
• Relations between the local chromatic number and its directed version
• Proper orientations and proper chromatic number
• Local chromatic number and distinguishing the strength of topological obstructions