Publikace na Matematicko-fyzikální fakulta |
2018
Abstrakt
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 rn edges, then alpha(2) (G) >= 6n-m-1/5.
By Euler's Formula, this implies alpha(2)(G) >= 4/5n. 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) >= 7/8n - 18n(3.)