Simple view
Full metadata view
Authors
Statistics
Improved bounds for weak coloring numbers
Journal
The Electronic Journal of Combinatorics
100
Author
Joret Gwenaël
Micek Piotr
Volume
29
Number
1
Article ID
P1.60
ISSN
1097-1440
eISSN
1077-8926
Language
English
Journal language
English
Abstract in English
Weak coloring numbers generalize the notion of degeneracy of a graph. They were introduced by Kierstead & Yang in the context of games on graphs. Recently, several connections have been uncovered between weak coloring numbers and various parameters studied in graph minor theory and its generalizations. In this note, we show that for every fixed
Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
Scopus© citations
5
cris.lastimport.wos | 2024-04-09T22:54:22Z | |
dc.abstract.en | Weak coloring numbers generalize the notion of degeneracy of a graph. They were introduced by Kierstead & Yang in the context of games on graphs. Recently, several connections have been uncovered between weak coloring numbers and various parameters studied in graph minor theory and its generalizations. In this note, we show that for every fixed $k≥1$, the maximum r-th weak coloring number of a graph with simple treewidth $k$ is $\Theta (r^{k-1}log r)$. As a corollary, we improve the lower bound on the maximum r-th weak coloring number of planar graphs from $\Omega (r^{2})$ to $\Omega (r^{2} log r)$, and we obtain a tight bound of $Θ$(r log r) for outerplanar graphs. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.contributor.author | Joret, Gwenaël | pl |
dc.contributor.author | Micek, Piotr - 142050 | pl |
dc.date.accessioned | 2023-02-20T09:11:29Z | |
dc.date.available | 2023-02-20T09:11:29Z | |
dc.date.issued | 2022 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 1 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 29 | pl |
dc.identifier.articleid | P1.60 | pl |
dc.identifier.doi | 10.37236/10274 | pl |
dc.identifier.eissn | 1077-8926 | pl |
dc.identifier.issn | 1097-1440 | pl |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/308006 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa | * |
dc.rights.licence | CC-BY-ND | |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/4.0/legalcode.pl | * |
dc.share.type | otwarte czasopismo | |
dc.subtype | Article | pl |
dc.title | Improved bounds for weak coloring numbers | pl |
dc.title.journal | The Electronic Journal of Combinatorics | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |
cris.lastimport.wos
2024-04-09T22:54:22Z dc.abstract.enpl
Weak coloring numbers generalize the notion of degeneracy of a graph. They were introduced by Kierstead & Yang in the context of games on graphs. Recently, several connections have been uncovered between weak coloring numbers and various parameters studied in graph minor theory and its generalizations. In this note, we show that for every fixed $k≥1$, the maximum r-th weak coloring number of a graph with simple treewidth $k$ is $\Theta (r^{k-1}log r)$. As a corollary, we improve the lower bound on the maximum r-th weak coloring number of planar graphs from $\Omega (r^{2})$ to $\Omega (r^{2} log r)$, and we obtain a tight bound of $Θ$(r log r) for outerplanar graphs. dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej dc.contributor.authorpl
Joret, Gwenaël dc.contributor.authorpl
Micek, Piotr - 142050 dc.date.accessioned
2023-02-20T09:11:29Z dc.date.available
2023-02-20T09:11:29Z dc.date.issuedpl
2022 dc.date.openaccess
0 dc.description.accesstime
w momencie opublikowania dc.description.numberpl
1 dc.description.version
ostateczna wersja wydawcy dc.description.volumepl
29 dc.identifier.articleidpl
P1.60 dc.identifier.doipl
10.37236/10274 dc.identifier.eissnpl
1077-8926 dc.identifier.issnpl
1097-1440 dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/308006 dc.languagepl
eng dc.language.containerpl
eng dc.rights*
Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa dc.rights.licence
CC-BY-ND dc.rights.uri*
http://creativecommons.org/licenses/by-nd/4.0/legalcode.pl dc.share.type
otwarte czasopismo dc.subtypepl
Article dc.titlepl
Improved bounds for weak coloring numbers dc.title.journalpl
The Electronic Journal of Combinatorics dc.typepl
JournalArticle dspace.entity.type
Publication Affiliations
Wydział Matematyki i Informatyki
Micek, Piotr
No affiliation
Joret, Gwenaël