Abstract: In many applications of graph theory to computer science, operations research, logic, and

game theory, people are interested in various notions of sparse graphsâ€”graphs with few edges.

Common examples include graph classes whose members have bounded maximum degree,

bounded genus, or bounded tree-width. Nesetril and Ossona de Mendez introduced a formal

classification of sparsity for infinite classes of finite graphs with the notion of classes with

bounded expansion and the more general notion of nowhere-dense classes. This classification,

which includes the motivating examples mentioned above, is informative as there are many

interesting properties shared by all such sparse classes. Furthermore, interesting properties

of specific classes can often be generalized to all classes, while results on general classes can

often be sharpened for specific classes. Additionally, this formulation is remarkably robust;

there are many apparently disparate notions that are in fact equivalent. In this talk I will

discuss how this theory has benefitted from the study of graph coloring games and graph

ordering games.