Coloring parameters for graphs on surfaces

We overview several coloring parameters with the property that they are bounded on graphs whose (Euler) genus is bounded. Besides the usual chromatic number, we treat the acyclic, the star and the degenerate chromatic number, we discuss some of their relatives, and we determine their dependence on the genus. Extensions to more general classes of graphs (minor-closed families and classes of bounded expansion) are also discussed. The probabilistic method, which is used in proving both upper and lower bounds, gives the dependence of the treated coloring parameters in terms of the maximum degree, a result which is of independent interest.