Improved bounds for weak coloring numbers

2022
journal article
article
5
cris.lastimport.wos2024-04-09T22:54:22Z
dc.abstract.enWeak 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.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorJoret, Gwenaëlpl
dc.contributor.authorMicek, Piotr - 142050 pl
dc.date.accessioned2023-02-20T09:11:29Z
dc.date.available2023-02-20T09:11:29Z
dc.date.issued2022pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number1pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume29pl
dc.identifier.articleidP1.60pl
dc.identifier.doi10.37236/10274pl
dc.identifier.eissn1077-8926pl
dc.identifier.issn1097-1440pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/308006
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa*
dc.rights.licenceCC-BY-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nd/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subtypeArticlepl
dc.titleImproved bounds for weak coloring numberspl
dc.title.journalThe Electronic Journal of Combinatoricspl
dc.typeJournalArticlepl
dspace.entity.typePublication
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

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.