The analysis reveals bounds on strong odd chromatic numbers in graph classes, indicating novel properties.
We prove that for every d∈ N and every graph class of bounded expansion C, there exists some c∈ N so that every graph from C admits a proper coloring with at most c colors satisfying the following condition: in every ball of radius d, every color appears either zero times or an odd number of times. For $d=1$, this provides a positive answer to a question raised by Goetze, Klute, Knauer, Parada, Peña, and Ueckerdt [ArXiv 2505.02736] about the boundedness of the strong odd chromatic number in graph classes of bounded expansion. The key technical ingredient towards the result is a proof that the strong odd coloring number of a sets system can be bounded in terms of its semi-ladder index, 2VC dimension, and the maximum subchromatic number among induced subsystems.
No takes yet. Share an insight, caveat, or question.
Michał Pilipczuk (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: