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 $\alpha_2(G)$. We prove that if $G$ is a connected triangle-free planar graph with $n$ vertices and $m$ edges, then $\alpha_2(G) \geq \frac{6n - m - 1}{5}$. By Euler's Formula, this implies $\alpha_2(G) \geq \frac{4}{5}n$. We also prove that if $G$ is a triangle-free planar graph on $n$ vertices with at most $n_3$ vertices of degree at most three, then $\alpha_2(G) \geq \frac{7}{8}n - 18 n_3$.
@article{10_37236_7311,
author = {Zden\v{e}k Dvo\v{r}\'ak and Tom Kelly},
title = {Induced 2-degenerate subgraphs of triangle-free planar graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7311},
zbl = {1391.05092},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7311/}
}
TY - JOUR
AU - Zdeněk Dvořák
AU - Tom Kelly
TI - Induced 2-degenerate subgraphs of triangle-free planar graphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7311/
DO - 10.37236/7311
ID - 10_37236_7311
ER -
%0 Journal Article
%A Zdeněk Dvořák
%A Tom Kelly
%T Induced 2-degenerate subgraphs of triangle-free planar graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7311/
%R 10.37236/7311
%F 10_37236_7311
Zdeněk Dvořák; Tom Kelly. Induced 2-degenerate subgraphs of triangle-free planar graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7311
