Geodesic
Bounding generalized coloring numbers of planar graphs using coin models
Jesper Nederlof1 ; Michał Pilipczuk2 ; Karol Węgrzycki3
1Utrecht University
2University of Warsaw
3Saarland University and Max Planck Institute for Informatics, Saarbrücken
The electronic journal of combinatorics, Tome 30 (2023) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and ordering the vertices by non-increasing radii of the associated discs. We prove that for every $d\in \mathbb{N}$, any such ordering has $d$-admissibility bounded by $O(d/\ln d)$ and weak $d$-coloring number bounded by $O(d^4 \ln d)$. This in particular shows that the $d$-admissibility of planar graphs is bounded by $O(d/\ln d)$, which asymptotically matches a known lower bound due to Dvořák and Siebertz.
DOI : 10.37236/11095
Classification : 05C15, 05C10, 05C62, 06A07
Mots-clés : Koebe orderings, weak \(d\)-coloring number

Jesper Nederlof  1   ; Michał Pilipczuk  2   ; Karol Węgrzycki  3

1 Utrecht University
2 University of Warsaw
3 Saarland University and Max Planck Institute for Informatics, Saarbrücken 
@article{10_37236_11095,
     author = {Jesper Nederlof and Micha{\l} Pilipczuk and Karol W\k{e}grzycki},
     title = {Bounding generalized coloring numbers of planar graphs using coin models},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {3},
     doi = {10.37236/11095},
     zbl = {1533.05097},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11095/}
}
TY  - JOUR
AU  - Jesper Nederlof
AU  - Michał Pilipczuk
AU  - Karol Węgrzycki
TI  - Bounding generalized coloring numbers of planar graphs using coin models
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11095/
DO  - 10.37236/11095
ID  - 10_37236_11095
ER  - 
%0 Journal Article
%A Jesper Nederlof
%A Michał Pilipczuk
%A Karol Węgrzycki
%T Bounding generalized coloring numbers of planar graphs using coin models
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11095/
%R 10.37236/11095
%F 10_37236_11095
Jesper Nederlof; Michał Pilipczuk; Karol Węgrzycki. Bounding generalized coloring numbers of planar graphs using coin models. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11095

Cité par Sources :