Paperlane

no. 14 · Friday 13 November 2026

Boolean combinations of graphs

Sarosh Adenwalla, Samuel Braunfeld, John Sylvester and Viktor Zamaraev

math.CO · v2

Abstract

Boolean combinations allow combining given combinatorial objects to obtain new, potentially more complicated, objects. In this paper, we initiate a systematic study of this idea applied to graphs. In order to understand expressive power and limitations of boolean combinations in this context, we investigate how they affect different combinatorial and structural properties of graphs, in particular $χ$-boundedness, as well as characterize the structure of boolean combinations of graphs from various classes.

journal
The Electronic Journal of Combinatorics, 33(4), #P4.12, 2026
fields
Combinatorics
pdf ↗ page arXiv:2412.19551 ↗