Certain measures of graphs, such as the edge coloring number, are hard to compute precisely. Some others, such as the maximum number of vertex-disjoint cycles, are even hard to approximate. It is known, for example, that computing &mgr;(G), the maximum number of vertex-disjoint cycles, is a nondeterministic polynomial time (NP) complete problem, and further that &mgr;(G) cannot be approximated easily.

Thus, the current work presents a beautiful and aesthetically pleasing result that proves that &mgr;(G) is bounded between [&bgr;(G)-2 &ggr;M(G)] and [&bgr;(G) - &ggr;M(G)]. Here &bgr;(G) is the cycle rank of the undirected graph G, which is simply m-n+1. (We note that the cycle rank of a directed graph is an entirely different measure, which is not easily computable itself.) &ggr;M(G) is the maximum genus of G, that is, the largest integer g such that G has a cellular embedding into the orientable surface of genus g. Both the bounds are computable in polynomial time. An interesting aspect of Kotrbčik’s result is that the bounds are shown to be tight for infinitely many graphs. Therefore, the bounds cannot be improved directly without considering special classes of graphs. Different bounds that use different measures may still be provable, and those bounds may be tighter or less tight than Kotrbčik’s bounds, depending on the actual instance of the graph.

Also, it is worth noting that this result builds on a thorough understanding of previous results by Xuong and Nebesk¿, not merely in using the results, but also in leveraging the proof for the construction of the main theorem.

Besides the obvious improvements that better bounds for measures can lead to in the branch-and-bound algorithms, we observe that this work also goes far in establishing the deficiency of graph G as a very relevant measure in cycle packing number discussions.