2017/09/12 by Dvořák, Zdeněk, Kelly, Tom · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1709.04036
A graph is k-degenerate if every subgraph has minimum degree at most k. We provide lower bounds on the size of a maximum induced 2-degenerate subgraph in a triangle-free planar graph. We denote the size of a maximum induced 2-degenerate subgraph of a graph G by α2(G). We prove that if G is a connected triangle-free planar graph with n vertices and m edges, then α2(G) ≥ (6n - m - 1)/(5). By Euler's Formula, this implies α2(G) ≥ (4)/(5)n. We also prove that if G is a triangle-free planar graph on n vertices with at most n3 vertices of degree at most three, then α2(G) ≥ (7)/(8)n - 18 n3.