Geodesic
Strong odd colorings in graph classes of bounded expansion
Michał Pilipczuk1
1University of Warsaw
The electronic journal of combinatorics, Tome 32 (2025) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that for every $d\in \mathbb{N}$ and every graph class of bounded expansion $\mathscr{C}$, there exists some $c\in \mathbb{N}$ so that every graph from $\mathscr{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.
DOI : 10.37236/14259
Classification : 05C15
Mots-clés : odd coloring, strong odd coloring, sparse graph, graph of bounded expansion

Michał Pilipczuk  1

1 University of Warsaw 
@article{10_37236_14259,
     author = {Micha{\l} Pilipczuk},
     title = {Strong odd colorings in graph classes of bounded expansion},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {4},
     doi = {10.37236/14259},
     zbl = {8120100},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/14259/}
}
TY  - JOUR
AU  - Michał Pilipczuk
TI  - Strong odd colorings in graph classes of bounded expansion
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/14259/
DO  - 10.37236/14259
ID  - 10_37236_14259
ER  - 
%0 Journal Article
%A Michał Pilipczuk
%T Strong odd colorings in graph classes of bounded expansion
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/14259/
%R 10.37236/14259
%F 10_37236_14259
Michał Pilipczuk. Strong odd colorings in graph classes of bounded expansion. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/14259

Cité par Sources :