A Boolean combination of graphs 
on the same vertex set 
is a simple graph 
whose adjacency indicators are obtained by applying a fixed
Boolean function 
:
 |
The diagonal of the adjacency matrix is set to zero, so negating an input does not create graph loops (Chandoo 2023, pp. 17-18; Adenwalla et al. 2026, pp. 8-9).
The conjunction and disjunction functions give graph intersection and graph union, respectively. Negation gives graph complement, and exclusive disjunction gives the symmetric difference of the edge sets.
For a fixed positive integer 
, a graph intersection
of 
split graphs satisfies 
, where 
is the chromatic number
and 
is the clique number. More generally, every Boolean
combination of at most 
split graphs satisfies
 |
The number 
must be fixed when this is interpreted as a bound on a class of graphs
(Adenwalla et al. 2026, pp. 29-30).
