The independence ratio of 4-cycle-free planar graphs

Autor:	Kelly, Tom, Kolichala, Sid, McFarland, Caleb, Su, Jatong
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C10 05C69
Druh dokumentu:	Working Paper
Popis:	We prove that every $n$-vertex planar graph $G$ with no triangle sharing an edge with a 4-cycle has independence ratio $n/\alpha(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$. Comment: 12 pages, 3 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2305.02414 Zobrazit plný text záznamu View this record from Arxiv