2017/02/09 by Zdenĕk Dvořák, Dvořák, Zdeněk, Jordan Venters +1
Computer Science · Mathematics · #05C69 (Primary) #05C85 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1702.02888
openalex publication_date 2017/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Since planar triangle-free graphs are 3-colourable, such a graph with n vertices has an independent set of size at least n/3. We prove that unless the graph contains a certain obstruction, its independence number is at least n/(3-epsilon) for some fixed epsilon>0. We also provide a reduction rule for this obstruction, which enables us to transform any plane triangle-free graph G into a plane triangle-free graph G' such that alpha(G')-|G'|/3=alpha(G)-|G|/3 and |G'|<=(alpha(G)-|G|/3)/epsilon. We derive a number of algorithmic consequences as well as a structural description of n-vertex plane triangle-free graphs whose independence number is close to n/3.