On the generalized coloring numbers

The coloring number col ( G ) of a graph G , which is equal to the degeneracy of G plus one, provides a very useful measure for the uniform sparsity of G . The coloring number is generalized by three series of measures, the generalized coloring numbers . These are the r - admissibility adm r ( G ) , the strong r -coloring number col r ( G ) and the weak r -coloring number wcol r ( G ) , where r is an integer parameter. The generalized coloring numbers measure the edge density of bounded-depth minors and thereby provide an even more uniform measure of sparsity of graphs. They have found many applications in graph theory and in particular play a key role in the theory of bounded expansion and nowhere dense graph classes introduced by Nešetřil and Ossona de Mendez. We overview combinatorial and algorithmic applications of the generalized coloring numbers, emphasizing new developments in this area. We also present a simple proof for the existence of uniform orders and improve known bounds, e.g., for the weak coloring numbers on graphs with excluded topological minors.