  E-graphs are a prominent data structure that has been increasing in
popularity in recent years due to their expanding range of applications in
various formal reasoning tasks. Often, they are used for equality saturation, a
process of deriving consequences through repeatedly applying universally
quantified equality formulas via term rewriting. They handle equality reasoning
over a large spaces of terms, but are severely limited in their handling of
case splitting and other types of logical cuts, especially when compared to
other reasoning techniques such as sequent calculi and resolution. The main
difficulty is when equality reasoning requires multiple inconsistent
assumptions to reach a single conclusion. Ad-hoc solutions, such as duplicating
the e-graph for each assumption, are available, but they are notably
resource-intensive.
  We introduce a key observation is that each duplicate e-graph (with an added
assumption) corresponds to coarsened congruence relation. Based on that, we
present an extension to e-graphs, called Colored E-Graphs, as a way to
represent all of the coarsened congruence relations in a single structure. A
colored e-graph is a memory-efficient equivalent of multiple copies of an
e-graph, with a much lower overhead. This is attained by sharing as much as
possible between different cases, while carefully tracking which conclusion is
true under which assumption. Support for multiple relations can be thought of
as adding multiple "color-coded" layers on top of the original e-graph
structure, leading to a large degree of sharing.
  In our implementation, we introduce optimizations to rebuilding and
e-matching. We run experiments and demonstrate that our colored e-graphs can
support hundreds of assumptions and millions of terms with space requirements
that are an order of magnitude lower, and with similar time requirements.
