Record link: 
http://hdl.handle.net/20.500.12708/144395
-
Title: 
Twin-width and generalized coloring numbers
en
Citation: 
Dreier, J., Gajarský, J., Jiang, Y., Ossona de Mendez, P., & Raymond, J.-F. (2022). Twin-width and generalized coloring numbers. Discrete Mathematics, 345(3), Article 112746. https://doi.org/10.1016/j.disc.2021.112746
-
Publisher DOI: 
10.1016/j.disc.2021.112746
-
Publication Type: 
Article - Original Research Article
en
Language: 
English
-
Authors: 
Dreier, Jan 
Gajarský, Jakub 
Jiang, Yiting 
Ossona de Mendez, Patrice 
Raymond, Jean-Florent 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Journal: 
Discrete Mathematics 
-
ISSN: 
0012-365X
-
Date (published): 
Mar-2022
-
Number of Pages: 
8
-
Publisher: 
ELSEVIER
-
Peer reviewed: 
Yes
-
Keywords: 
Generalized coloring numbers; Twin-width; Permutations; bounded expansion; admissibility
en
Abstract: 
In this paper, we prove that a graph G with no Ks,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.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Article

Show full item record

Page view(s)

184
checked on Nov 23, 2023

Download(s)

5
checked on Nov 23, 2023

Google ScholarTM

Check