The Independence Ratio of 4‐Cycle‐Free Planar Graphs

Journal of Graph Theory 2026 Open access

Read full text
Authors: Tom Kelly, Sid Kolichala, Caleb McFarland, Jatong Su
DOI: 10.1002/jgt.70020
Cited by: 0
References: 40

Abstract

ABSTRACT We prove that every ‐vertex planar graph with no triangle sharing an edge with a 4‐cycle has independence ratio for . 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 .

Fields of Study & Subjects

Advanced Graph Theory Research Computational Geometry and Mesh Generation Limits and Structures in Graph Theory

Publication details

Journal / source
Journal of Graph Theory
Volume
112
Issue
2
Pages
116–127
Publication date
15 March 2026
Language
EN