Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915580995436544 |
|---|---|
| author | Enami, Kengo Matsumoto, Naoki Yashima, Takamasa |
| author_facet | Enami, Kengo Matsumoto, Naoki Yashima, Takamasa |
| contents | Two of the most prominent unresolved conjectures in graph theory, the Albertson-Berman conjecture and the Matheson-Tarjan conjecture, have been extensively studied by many researchers.
(AB) Every planar graph of order $n$ has an induced forest of order at least $\frac{n}{2}$.
(MT) Every plane triangulation of sufficiently large order $n$ has a dominating set of cardinality at most $\frac{n}{4}$.
Although partial progress and weaker bounds are known, both conjectures remain unsolved. To shed further light on them, researchers have explored a variety of related notions and generalizations. In this paper, we clarify relations among several of these notions, most notably connected domination and induced outerplanar subgraphs, and investigate the corresponding open problems. Furthermore, we construct an infinite family of plane triangulations of order $n$ whose connected domination number exceeds $n/3$. This construction gives a negative answer to a question of Bradshaw et al. [SIAM J. Discrete Math. 36 (2022) 1416-1435], who asked whether the maxleaf number of every plane triangulation of order $n$ is at least $2n/3$. We also obtain new results on induced subgraphs with bounded treewidth and induced outerplanar subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10471 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets Enami, Kengo Matsumoto, Naoki Yashima, Takamasa Discrete Mathematics Combinatorics 05C10, 05C35, 05C69 Two of the most prominent unresolved conjectures in graph theory, the Albertson-Berman conjecture and the Matheson-Tarjan conjecture, have been extensively studied by many researchers. (AB) Every planar graph of order $n$ has an induced forest of order at least $\frac{n}{2}$. (MT) Every plane triangulation of sufficiently large order $n$ has a dominating set of cardinality at most $\frac{n}{4}$. Although partial progress and weaker bounds are known, both conjectures remain unsolved. To shed further light on them, researchers have explored a variety of related notions and generalizations. In this paper, we clarify relations among several of these notions, most notably connected domination and induced outerplanar subgraphs, and investigate the corresponding open problems. Furthermore, we construct an infinite family of plane triangulations of order $n$ whose connected domination number exceeds $n/3$. This construction gives a negative answer to a question of Bradshaw et al. [SIAM J. Discrete Math. 36 (2022) 1416-1435], who asked whether the maxleaf number of every plane triangulation of order $n$ is at least $2n/3$. We also obtain new results on induced subgraphs with bounded treewidth and induced outerplanar subgraphs. |
| title | Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets |
| topic | Discrete Mathematics Combinatorics 05C10, 05C35, 05C69 |
| url | https://arxiv.org/abs/2506.10471 |