Strong odd colorings in graph classes of bounded expansion

Michał Pilipczuk · 2025

Read Strong odd colorings in graph classes of bounded expansion by Michał Pilipczuk (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-2505-15288.txt.

Introduction

Michał Pilipczuk proves that sparse graph families admit a strong form of odd coloring, in a 2025 paper. A strong odd coloring paints a graph's points so that neighbors differ. Inside any ball of a fixed radius, each color must also show up either not at all or an odd number of times. Whether few colors always suffice for graph classes of bounded expansion was an open question for radius one.

Pilipczuk shows a single color bound works for every radius at once in such classes. The key step bounds the coloring number of a set system using three of its measures. Those are a ladder index, a dimension measure, and the worst coloring number among its subsystems. The result settles the radius-one question as a special case.

Catalog record

CREATORMichał Pilipczuk
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15288

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strong odd colorings in graph classes of bounded expansion Michał Pilipczuk Abstract We prove that for every d ∈ ℕ d\in\mathbb{N} and a graph class of bounded expansion 𝒞 \mathscr{C} , there exists some c ∈ ℕ c\in\mathbb{N} so that every graph from 𝒞 \mathscr{C} admits a proper coloring with at most c c colors satisfying the following condition: in every ball of radius d d , every color appears either zero times or an odd number of times. For d = 1 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. Mi. P. was supported by the project BOBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. 1 Introduction Recall that a proper coloring of a graph G is a function \phi mapping vertices of G to some palette of colors, say C , so that for every two vertices u,v that are adjacent in G , we have \phi(u)\neq\phi(v) . Recently, Kwon and Park [ 9 ] introduced the concept of a strong odd coloring of a graph, which is a proper coloring that satisfies the following additional condition: for every vertex u and every color i\in C , the number of vertices of color i among the neighbors of u is either zero or odd. This is a strengthening of the notion of an odd coloring , where we only require that the coloring is proper and for every vertex u with a nonempty neighborhood, there exists a color that is featured an odd number of times among the neighbors of u . The (strong) odd chromatic number of a graph G is defined as the minimum number of colors needed for a (strong) odd coloring of G . Kwon and Park [ 9 ] proved several results relating the strong odd chromatic number of a graph and its maximum degree. They also asked whether the strong odd chromatic number is universally bounded on the class of planar graphs. This question was answered in positive by Caro et al. [ 2 ] , who proved that the strong odd chromatic number of every planar graph is at most 388 . Very recently, Goetze et al. [ 7 ] generalized this result by proving that every proper minor-closed class has bounded strong odd chromatic number. They also asked whether this conclusion is true even in the larger generality of graph classes of bounded expansion, which is a concept of uniform, local sparsity in graphs that underlies the theory of Sparsity of Nešetřil and Ossona de Mendez; see [ 12 ] for an introduction. Note that, as proved by Hickingbotham [ 8 ] and by Liu [ 10 ] , graph classes of bounded expansion have bounded odd chromatic number. In this paper we answer the question of Goetze et al. [ 7 ] in positive. Theorem 1.1 . Every graph class of bounded expansion has bounded strong odd chromatic number. In fact, we prove a more general statement that speaks about balls of any fixed radius d , instead of just neighborhoods. Theorem 1.2 . Let d\in\mathbb{N} and \mathscr{C} be a graph class of bounded expansion. Then there exists c\in\mathbb{N} such that for every graph G\in\mathscr{C} there exists a proper coloring of G with c colors satisfying the following condition: for every vertex u of G and color i , the number of vertices of color i that are at distance at most d from u is either zero or odd. Note that Theorem 1.1 follows from Theorem 1.2 for d=1 . Indeed, if \phi is a proper coloring of a graph G such that in every radius- 1 ball, say around a vertex u , every color is featured zero times or an odd number, then this is also true for the (open) neighborhood N_{G}(u) , because the color of u is not featured among the colors present in N_{G}(u) (due to \phi being proper). The core element of our proof is the following statement about strong odd colorings of set systems; that is, colorings of the universe of the set system so that every set in the family contains every color zero times or an odd number of times. Precisely, we bound the odd chromatic number of a set system in terms of three parameters: the semi-ladder index, the 2VC dimension, and the maximum subchromatic number among the induced subsystems (see Sections 2 and 3 for definitions). Theorem 1.3 . There is a function f\colon\mathbb{N}^{3}\to\mathbb{N} such that the following holds. Suppose \mathcal{S} is a set system with semi-ladder index at most \ell , 2VC dimension at most h , and whose every induced subsystem has subchromatic number at most s , for some \ell,h,s\in\mathbb{N} . Then the strong odd chromatic number of \mathcal{S} is at most f(\ell,h,s) . The proof of Theorem 1.3 , presented in Section 4 , proceeds by induction on the semi-ladder index. The boundedness of the 2VC dimension is exploited through a duality result of Ding et al. [ 3 ] , whereas the boundedness of the subchromatic index is used to design the induction so that the semi-ladder index drops with every induction step. To derive Theorem 1.2 from Theorem 1.3 , it suffices to show that for every d\in\mathbb{N} and graph class of bounded expansion \mathscr{C} , the class of set systems of radius- d balls in graphs from \mathscr{C} has all the relevant parameters bounded. This was explicitly proved for the semi-ladder index by Fabiański et al. [ 4 ] , for the 2VC dimension by Pilipczuk and Siebertz [ 16 ] , and for the subchromatic number by Nešetřil et al. [ 13 ] . However, the last proof applies only to the whole set system of balls, and not to its induced subsystems. Hence, in Section 3 we propose a new argument that suitably strengthens the result of [ 13 ] . 2 Preliminaries By \mathbb{N} we denote the set of nonnegative integers. For a positive integer p , we write [p]\coloneqq\{1,\ldots,p\} . Graphs. We use standard graph notation. All graphs in this paper are finite, undirected, and simple, that is, without loops or parallel edges. For a graph G , by V(G) we denote the vertex set of G . For A\subseteq V(G) , G[A] denotes the subgraph induced by A , which is the graph on vertex set A where any two vertices are adjacent if and only if they are adjacent in G . A graph parameter is a mapping that assigns each graph a nonnegative integer. A graph class is simply a set of graphs, typically infinite. For a graph parameter \pi and a graph class \mathscr{C} , we say that \mathscr{C} has bounded \pi if there is a constant c\in\mathbb{N}

Read the complete text