Skip to main content
x

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

Authors
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)