  We study the integrality gap of the natural linear programming relaxation for
the \textit{Bounded Color Matching} (BCM) problem. We provide several families
of instances and establish lower bounds on their integrality gaps and we study
how the Sherali-Adams "lift-and-project" technique behaves on these instances.
We complement these results by showing that if we exclude certain simple
sub-structures from our input graphs, then the integrality gap of the natural
linear formulation strictly improves. To prove this, we adapt for our purposes
the results of F\"{u}redi [\emph{Combinatorica}, 1(2):155-162, 1981]. We
further leverage this to show upper bounds on the performance of the
Sherali-Adams hierarchy when applied to the natural LP relaxation of the BCM
problem.
