  Bounded expansion and nowhere-dense classes of graphs capture the theoretical
tractability for several important algorithmic problems. These classes of
graphs can be characterized by the so-called weak coloring numbers of graphs,
which generalize the well-known graph invariant degeneracy (also called k-core
number). Being NP-hard, weak-coloring numbers were previously computed on
real-world graphs mainly via incremental heuristics. We study whether it is
feasible to augment such heuristics with exponential-time subprocedures that
kick in when a desired upper bound on the weak coloring number is breached. We
provide hardness and tractability results on the corresponding computational
subproblems. We implemented several of the resulting algorithms and show them
to be competitive with previous approaches on a previously studied set of
benchmark instances containing 86 graphs with up to 183831 edges. We obtain
improved weak coloring numbers for over half of the instances.
