
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 $\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$.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), graph degeneracy, planar graphs, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, discharging, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), coloring number, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), graph degeneracy, planar graphs, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, discharging, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), coloring number, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
