Boolean Combinations of Graphs

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 $\chi$-boundedness, as well as characterize the structure of Boolean combinations of graphs from various classes.