The independence ratio of 4-cycle-free planar graphs

Abstract

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)\le 4-\epsilon$ for $\epsilon =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 $\epsilon =2/9$.

14 pages, 4 figures

References in corpus (2)

• 3-coloring triangle-free planar graphs with a precolored 8-cycle
• 3-coloring triangle-free planar graphs with a precolored 9-cycle