$\chi$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs

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.

15 pages. Changes in v2: extended introduction and minor corrections