On nowhere dense graphs

摘要: In this paper, we define and analyze the nowhere dense classes of graphs. This notion is a common generalization proper minor closed classes, graphs with bounded degree, locally planar graphs, expansion, to name just few which are studied extensively in combinatorial computer science contexts. show that concept leads classification general dichotomy between somewhere classes. surprisingly stable as it can be expressed terms most commonly used basic parameters, such independence number @a, clique @w, chromatic @g. The remarkable stability its robustness has applications mathematical logic, complexity algorithms, combinatorics. We also express versus edge densities trichotomy theorem.