Uniform Orderings for Generalized Coloring Numbers

Autor:	Heuvel, Jan van den, Kierstead, H. A.
Rok vydání:	2019
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C75
Druh dokumentu:	Working Paper
Popis:	The generalized coloring numbers col_r(G) (also denoted by scol_r(G)) and wcol_r(G) of a graph G were introduced by Kierstead and Yang as a generalization of the usual coloring number, and have found important theoretical and algorithmic applications. For each distance r, these numbers are determined by an "optimal" ordering of the vertices of G. We study the question of whether it is possible to find a single "uniform" ordering that is "good" for all distances r. We show that the answer to this question is essentially "yes". Our results give new characterizations of graph classes with bounded expansion and nowhere dense graph classes. Comment: 17 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1907.12149 Zobrazit plný text záznamu View this record from Arxiv