  A k-plex in a graph is a vertex set where each vertex is non-adjacent to at
most k vertices (including itself) in this set, and the Maximum k-plex Problem
(MKP) is to find the largest k-plex in the graph. As a practical NP-hard
problem, MKP has many important real-world applications, such as the analysis
of various complex networks. Branch-and-bound (BnB) algorithms are a type of
well-studied and effective exact algorithms for MKP. Recent BnB MKP algorithms
involve two kinds of upper bounds based on graph coloring and partition,
respectively, that work in different perspectives and thus are complementary
with each other. In this paper, we first propose a new coloring-based upper
bound, termed Relaxed Graph Color Bound (RelaxGCB), that significantly improves
the previous coloring-based upper bound. We further propose another new upper
bound, termed RelaxPUB, that incorporates RelaxGCB and a partition-based upper
bound in a novel way, making use of their complementarity. We apply RelaxGCB
and RelaxPUB to state-of-the-art BnB MKP algorithms and produce eight new
algorithms. Extensive experiments using diverse k values on hundreds of
instances based on dense and massive sparse graphs demonstrate the excellent
performance and robustness of our proposed methods.
