The independence ratio of 4-cycle-free planar graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912969706700800 |
|---|---|
| author | Kelly, Tom Kolichala, Sid McFarland, Caleb Su, Jatong |
| author_facet | Kelly, Tom Kolichala, Sid McFarland, Caleb Su, Jatong |
| contents | We prove that every $n$-vertex planar graph $G$ with no triangle sharing an edge with a 4-cycle has independence ratio $n/α(G) \leq 4 - \varepsilon$ for $\varepsilon = 1/30$. This result implies that the same bound holds for 4-cycle-free planar graphs and planar graphs with no adjacent triangles and no triangle sharing an edge with a 5-cycle. For the latter case we strengthen the bound to $\varepsilon = 2/9$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02414 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The independence ratio of 4-cycle-free planar graphs Kelly, Tom Kolichala, Sid McFarland, Caleb Su, Jatong Combinatorics Discrete Mathematics 05C10, 05C69 We prove that every $n$-vertex planar graph $G$ with no triangle sharing an edge with a 4-cycle has independence ratio $n/α(G) \leq 4 - \varepsilon$ for $\varepsilon = 1/30$. This result implies that the same bound holds for 4-cycle-free planar graphs and planar graphs with no adjacent triangles and no triangle sharing an edge with a 5-cycle. For the latter case we strengthen the bound to $\varepsilon = 2/9$. |
| title | The independence ratio of 4-cycle-free planar graphs |
| topic | Combinatorics Discrete Mathematics 05C10, 05C69 |
| url | https://arxiv.org/abs/2305.02414 |