2020/07/13 by Prosenjit Bose, Vida Dujmović, Bose, Prosenjit +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2007.06455
openalex publication_date 2020/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A (vertex) ℓ-ranking is a colouring φ:V(G)→ℕ of the vertices of a graph G with integer colours so that for any path u0,…,up of length at most ℓ, φ(u0)≠φ(up) or φ(u0)<max\φ(u0),…,φ(up)\. We show that, for any fixed integer ℓ≥ 2, every n-vertex planar graph has an ℓ-ranking using O(log n/logloglog n) colours and this is tight even when ℓ=2; for infinitely many values of n, there are n-vertex planar graphs, for which any 2-ranking requires Ω(log n/logloglog n) colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for ℓ-ranking graphs of treewidth t and graphs of simple treewidth t. These upper bounds are constructive and give O(n)-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for ℓ-rankings of apex minor-free graphs and k-planar graphs.