The independence ratio of 4-cycle-free planar graphs
This work addresses graph theory problems for researchers in combinatorics and theoretical computer science, providing incremental improvements to known bounds on independence ratios in planar graphs.
The paper proves that planar graphs without triangles sharing an edge with a 4-cycle have an independence ratio bounded by 4 - 1/30, extending this result to 4-cycle-free planar graphs and planar graphs with no adjacent triangles and no triangle sharing an edge with a 5-cycle, with a stronger bound of 4 - 2/9 in the latter case.
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$.