χ \chi -Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Marthe Bonamy, Colin Geniet · 2025
Read χ \chi -Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs by Marthe Bonamy, Colin Geniet (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-2504-08266.txt.
Introduction
Marthe Bonamy and Colin Geniet prove basic behavior for a fresh graph family in this 2025 note, given in short form. The family, bounded merge-width graphs, unites two older tame classes, and logic queries stay tractable on it. The authors show three traits the older classes share carry over. The graphs are chi-bounded, meaning their coloring needs stay tied to their clique size. They show the strong Erdős-Hajnal property, a promise of large tidy substructures. The count of distinct neighborhoods grows only linearly with size.
Catalog record
| CREATOR | Marthe Bonamy, Colin Geniet |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08266
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
χ \chi -Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs Marthe Bonamy, Colin Geniet Abstract Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem remains tractable. We prove that a number of basic properties shared by bounded expansion and bounded twin-width graphs also hold for bounded merge-width graphs: they are χ \chi -bounded, they satisfy the strong Erdős–Hajnal property, and their neighbourhood complexity is linear. 1 Introduction Dreier and Toruńczyk introduced merge-width in [ DT25 ] as the next step in the program of characterising the graph classes that have fixed parameter tractable algorithms for first-order model checking—the problem of testing a given first-order formula \phi on a given graph G . Bounded merge-width classes admit such an algorithm (assuming appropriate witnesses of merge-width are given), and encompass both bounded expansion classes and bounded twin-width classes, thus unifying the known model checking algorithms for the latter two [ DKT13 , BKTW22 ] . Merge-width is conjectured to be equivalent to flip-width , previously introduced by Toruńczyk with similar goals [ Tor23 ] , but for which the model checking problem remains open. In this work, we show with elementary proofs that merge-width satisfies a few classical graph theoretic properties, the most significant being \chi -boundedness . This generalises on the one hand the simple remark that bounded expansion graphs are degenerate, and thus have bounded chromatic number, and on the other hand the fact that bounded clique-width [ DK12 ] and bounded twin-width [ BGK+21 ] graphs are \chi -bounded. We leave open the question of polynomial \chi -boundedness, which in the case of clique-width and twin-width required the introduction of much more involved tools [ BP20 , PS23 , BT25 ] . Merge-width is defined through merge sequences : for a graph G , a merge sequence consists of (\mathcal{P}_{1},R_{1}),\dots,(\mathcal{P}_{m},R_{m}) where: 1. Each \mathcal{P}_{i} is a partition of V(G) , with \mathcal{P}_{1}=\{\{x\}:x\in V(G)\} being the partition into singletons, \mathcal{P}_{m}=\{V(G)\} being the trivial partition, and each \mathcal{P}_{i} being coarser than (or equal to) \mathcal{P}_{i-1} , meaning that each part P\in\mathcal{P}_{i} is obtained by merging any number of parts of \mathcal{P}_{i-1} . 2. R_{1}\subseteq\dots\subseteq R_{m}\subseteq\binom{V(G)}{2} is a monotone sequence of sets of resolved pairs . 3. For any two (possibly equal) parts A,B\in\mathcal{P}_{i} , the pairs in AB\setminus R_{i} (i.e. the unresolved pairs between A and B ) are either all edges, or all non-edges in G . To restrict merge sequences, one defines their width , parametrised by a radius r\in\mathbb{N} : it is the maximum over all steps i\geqslant 2 and vertices v\in V(G) of the number of parts in \mathcal{P}_{i-1} accessible from v by a path of length at most r in the graph (V(G),R_{i}) of resolved pairs. The mismatch of indices between \mathcal{P}_{i-1} and R_{i} is intentional, and prevents one from simultaneously merging too many parts and adding too many resolved pairs when going from (\mathcal{P}_{i-1},R_{i-1}) to (\mathcal{P}_{i},R_{i}) . The radius- r merge-width of G , denoted by \mw_{r}(G) , is the minimum radius- r width of a merge sequence for G . A class \mathcal{C} of graphs has bounded merge-width if there is a function f such that any G\in\mathcal{C} satisfies \mw_{r}(G)\leqslant f(r) for all r . We will show that bounded merge-width classes have the strong Erdős–Hajnal property, are \chi -bounded, and have linear neighbourhood complexity. All three properties were previously known to hold in bounded expansion classes and bounded twin-width classes, and the first two generalisations were conjectured in [ DT25 , Section 1, Discussion] . Linear neighbourhood complexity also generalises to bounded flip-width classes. We show that it is enough to bound merge-width (or flip-width) at radius 1 or 2 to obtain these results. At the core of our proofs is a technique sometimes called freezing , previously used in the context of twin-width [ BGK+21 , GPT22 ] . Freezing reduces the study of a merge-sequence \mathcal{P}_{1},\dots,\mathcal{P}_{m} to a single, judiciously chosen partition. In its simplest form, this means looking at the first (or last) step i for which \mathcal{P}_{i} satisfies the desired property. The more general form of freezing creates a new partition \mathcal{P} across \mathcal{P}_{1},\dots,\mathcal{P}_{m} , by considering the inclusion-wise maximal parts satisfying the property of interest. That is, for each vertex v , one considers the maximum i such that the part P\in\mathcal{P}_{i} containing v satisfies the desired property, and \mathcal{P} is defined as the collection of all such P . 1.1 Strong Erdős–Hajnal property The strong Erdős–Hajnal property refers to the presence of linear-size bicliques or anti-bicliques. Bounded twin-width classes were shown to satisfy this property in [ BGK+21 , Theorem 22] with a very simple proof. For bounded expansion classes, it is an immediate corollary of degeneracy. We show in Section 3 that the same holds for bounded radius-1 merge-width. Theorem 1.1 . Any graph G with n vertices satisfying \mw_{1}(G)=k contains disjoint subsets A,B of size \Omega(\frac{n}{k^{2}}) such that A,B are either complete or anti-complete. Our proof is inspired by the one for twin-width: we consider the first step i in the merge sequence such that \mathcal{P}_{i} has a part of size at least \varepsilon n , for a well chosen \varepsilon . 1.2 \chi -boundedness Next, we prove in Section 4 that any class \mathcal{C} of graphs with bounded merge-width is \chi -bounded: the chromatic number \chi(G) is bounded by some function of the size of a maximum clique \omega(G) . Precisely: Theorem 1.2 . Any graph G with \mw_{2}(G)\leqslant k and \omega(G)\leqslant t satisfies \chi(G)\leqslant(t+1)!k^{2t-2}. Bounded expansion classes are \chi -bounded in a trivial sense: they are degenerate, and thus have bounded chromatic number (and clique number). Bounded twin-width classes were shown to be \chi -bounded in [ BGK+21 , Theorem 21] . This was improved to reach polynomial \chi -boundedness in [ PS23 , BT25 ] , i.e. when twin-width is fixed, the chromatic number is bounded by a polynomial function of the clique number. Dreier and Toruńczyk also asked whether the same holds for bounded merge-width. Conjecture 1.3 ( [ DT25 ] ) . Bounded merge-width classes are polynomially \chi -bounded. In our proof of Theorem 1.2 we use merge-width at radius 2. It is unclear to us whether this is necessary, or radius 1 can suffice. Question 1.4 . Is the class \{G:\mw_{1}(G)\leqslant k\} , with k arbitrary, \chi -bounded? Specifically, radius-2 merge-width is used in Lemma 4.1 , while the remainder of our proof only requires a bound on radius-1 merge-width. It may be that Lemma 4.1 can be improved or modified to answer Question 1.4 positively. Conversely, one may answer it negatively by constructing a class \mathcal{C} of graphs with bounded radius-1 merge-width and bounded clique number (possibly even triangle-free), but unbounded chromatic number. Such a class \mathcal{C} needs to contain arbitrarily large bicliques: indeed graphs with bounded radius-1 merge-width and no biclique K_{t,t} as subgraph are degenerate [ DT25 , Corollary 7.7] , and thus have bounded chromatic number. On the other hand, \mathcal{C} having bounded radius-1 merge-width requires it to have bounded symmetric difference [ DT25 , Lemma 7.20] , meaning that graphs in \mathcal{C} and all their induced subgraphs must contain