A graph $G$ is $k$-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $d \ge 2$ has a $4$-degenerate induced subgraph containing at least $ (38 - d)/36$ of its vertices. This shows that every planar graph of order $n$ has a $4$-degenerate induced subgraph of order more than $8/9 \cdot n$. We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.
@article{10_37236_4265,
author = {Robert Lukot'ka and J\'an Maz\'ak and Xuding Zhu},
title = {Maximum 4-degenerate subgraph of a planar graph},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4265},
zbl = {1305.05056},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4265/}
}
TY - JOUR
AU - Robert Lukot'ka
AU - Ján Mazák
AU - Xuding Zhu
TI - Maximum 4-degenerate subgraph of a planar graph
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4265/
DO - 10.37236/4265
ID - 10_37236_4265
ER -
%0 Journal Article
%A Robert Lukot'ka
%A Ján Mazák
%A Xuding Zhu
%T Maximum 4-degenerate subgraph of a planar graph
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4265/
%R 10.37236/4265
%F 10_37236_4265
Robert Lukot'ka; Ján Mazák; Xuding Zhu. Maximum 4-degenerate subgraph of a planar graph. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4265
