Skip to main content

Twin-width and generalized coloring numbers

Authors Jan Dreier, Jakub Gajarský, Yiting Jiangc, Patrice Ossona de Mendez, Jean-Florent Raymond
Publication date 2021-11-28

In Twin-width and generalized coloring numbers 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\).

Discrete Mathematics, Volume 345, Issue 3, 2022, 11274

Jan Dreier (Vienna University of Technology, Austria)
Jakub Gajarský (University of Warsaw, Poland)
Yiting Jiangc (Université de Paris, CNRS, IRIF, F-75006, Paris, France; Department of Mathematics, Zhejiang Normal University, China)
Patrice Ossona de Mendez (Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557), Paris, France; Computer Science Institute of Charles University, Praha, Czech Republic)
Jean-Florent Raymond (CNRS, LIMOS, Université Clermont Auvergne, France)