Uniform Orderings for Generalized Coloring Numbers

2019/07/28 by Jan van den Heuvel, Heuvel, Jan van den, H. A. Kierstead +1 · 1 citation
Computer Science · Mathematics · #05C75 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C75

paper · pdf · doi:10.48550/arxiv.1907.12149

17 pages

arxiv created 2019/12/16 · arxiv updated 2019/12/18

Abstract

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.

Cited by

• Variants of Merge-Width and Applications

Related

• On the generalized coloring numbers
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
• The Generalised Colouring Numbers on Classes of Bounded Expansion
• Hardness of the Generalized Coloring Numbers
• Ordered Ramsey numbers of loose paths and matchings