Simple view
Full metadata view
Authors
Statistics
Bounded-degree planar graphs do not have bounded-degree product structure
Journal
Electronic Journal of Combinatorics
100
Author
Dujmović Vida
Joret Gwenaël
Micek Piotr
Morin Pat
Wood David
Volume
31
Number
2
Article ID
P2.51
ISSN
1077-8926
Access date
2025-01-20
Language
English
Journal language
English
Abstract in English
Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One particularly useful version states that every planar graph
Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
| dc.abstract.en | Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One particularly useful version states that every planar graph $G$ is contained in the strong product of a $3$-tree $H$, a path $P$, and a $3$-cycle $K_3$; written as $G\subseteq H\boxtimes P\boxtimes K_3$. A number of researchers have asked if this theorem can be strengthened so that the maximum degree in $H$ can be bounded by a function of the maximum degree in $G$. We show that no such strengthening is possible. Specifically, we describe an infinite family $\mathcal{G}$ of planar graphs of maximum degree $5$ such that, if an $n$-vertex member $G$ of $\mathcal{G}$ is isomorphic to a subgraph of $H\boxtimes P\boxtimes K_c$ where $P$ is a path and $H$ is a graph of maximum degree $\Delta$ and treewidth $t$, then $t\Delta c \ge 2^{\Omega(\sqrt{\log\log n})}$. | |
| dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | |
| dc.contributor.author | Dujmović, Vida | |
| dc.contributor.author | Joret, Gwenaël | |
| dc.contributor.author | Micek, Piotr - 142050 | |
| dc.contributor.author | Morin, Pat | |
| dc.contributor.author | Wood, David | |
| dc.date.accession | 2025-01-20 | |
| dc.date.accessioned | 2025-01-20T10:48:50Z | |
| dc.date.available | 2025-01-20T10:48:50Z | |
| dc.date.createdat | 2025-01-20T08:55:11Z | en |
| dc.date.issued | 2024 | |
| dc.date.openaccess | 0 | |
| dc.description.accesstime | w momencie opublikowania | |
| dc.description.number | 2 | |
| dc.description.version | ostateczna wersja wydawcy | |
| dc.description.volume | 31 | |
| dc.identifier.articleid | P2.51 | |
| dc.identifier.doi | 10.37236/11712 | |
| dc.identifier.issn | 1077-8926 | |
| dc.identifier.uri | https://ruj.uj.edu.pl/handle/item/545870 | |
| dc.identifier.weblink | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i2p51/pdf | |
| dc.language | eng | |
| dc.language.container | 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 | https://creativecommons.org/licenses/by-nd/4.0/legalcode.pl | |
| dc.share.type | otwarte czasopismo | |
| dc.subtype | Article | |
| dc.title | Bounded-degree planar graphs do not have bounded-degree product structure | |
| dc.title.journal | Electronic Journal of Combinatorics | |
| dc.type | JournalArticle | |
| dspace.entity.type | Publication | en |
dc.abstract.en
Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One particularly useful version states that every planar graph $G$ is contained in the strong product of a $3$-tree $H$, a path $P$, and a $3$-cycle $K_3$; written as $G\subseteq H\boxtimes P\boxtimes K_3$. A number of researchers have asked if this theorem can be strengthened so that the maximum degree in $H$ can be bounded by a function of the maximum degree in $G$. We show that no such strengthening is possible. Specifically, we describe an infinite family $\mathcal{G}$ of planar graphs of maximum degree $5$ such that, if an $n$-vertex member $G$ of $\mathcal{G}$ is isomorphic to a subgraph of $H\boxtimes P\boxtimes K_c$ where $P$ is a path and $H$ is a graph of maximum degree $\Delta$ and treewidth $t$, then $t\Delta c \ge 2^{\Omega(\sqrt{\log\log n})}$. dc.affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej dc.contributor.author
Dujmović, Vida dc.contributor.author
Joret, Gwenaël dc.contributor.author
Micek, Piotr - 142050 dc.contributor.author
Morin, Pat dc.contributor.author
Wood, David dc.date.accession
2025-01-20 dc.date.accessioned
2025-01-20T10:48:50Z dc.date.available
2025-01-20T10:48:50Z dc.date.createdaten
2025-01-20T08:55:11Z dc.date.issued
2024 dc.date.openaccess
0 dc.description.accesstime
w momencie opublikowania dc.description.number
2 dc.description.version
ostateczna wersja wydawcy dc.description.volume
31 dc.identifier.articleid
P2.51 dc.identifier.doi
10.37236/11712 dc.identifier.issn
1077-8926 dc.identifier.uri
https://ruj.uj.edu.pl/handle/item/545870 dc.identifier.weblink
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i2p51/pdf dc.language
eng dc.language.container
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
https://creativecommons.org/licenses/by-nd/4.0/legalcode.pl dc.share.type
otwarte czasopismo dc.subtype
Article dc.title
Bounded-degree planar graphs do not have bounded-degree product structure dc.title.journal
Electronic Journal of Combinatorics dc.type
JournalArticle dspace.entity.typeen
Publication Affiliations
No affiliation
Dujmović, Vida
Joret, Gwenaël
Morin, Pat
Wood, David
Wydział Matematyki i Informatyki
Micek, Piotr
computer and information sciences
