Twin-width and generalized coloring numbers

2021/04/19 by Dreier, Jan, Gajarsky, Jakub, Jiang, Yiting +2 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.09360

Abstract

In this paper, we prove that a graph G with no K_s,s-subgraph and twin-width d has r-admissibility and r-coloring numbers bounded from above by an exponential function of r and that we can construct graphs achieving such a dependency in r.

Cited by

• UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
• Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings

Related

• Graphs of bounded twin-width are quasi-polynomially χ-bounded
• On the generalized coloring numbers
• Twin-width II: small classes
• Twin-width VII: groups
• Twin-width and Transductions of Proper k-Mixed-Thin Graphs