Informace o publikaci
Twin-width of Planar Graphs; a Short Proof
| Autoři | |
|---|---|
| Rok publikování | 2025 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | EUROPEAN JOURNAL OF COMBINATORICS |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | arXiv preprint |
| Doi | http://dx.doi.org/10.1016/j.ejc.2024.104036 |
| Klíčová slova | twin-width; planar graph |
| Popis | The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction by Král’ and Lamaison (2022), and an upper bound of 8 by Hliněný and Jedelský (2022). The upper bound (currently best) of 8, however, is rather complicated and involved. In the paper we give a short and simple self-contained proof that the twin-width of planar graphs is at most 11. We believe that this short proof can also shed more light on the topic of upper bound(s) on the twin-width of planar and beyond-planar graphs in general. |