3-degenerate induced subgraph of a planar graph

Autor:	Gu, Y., Kierstead, H. A., Oum, Sang-il, Qi, Hao, Zhu, Xuding
Rok vydání:	2020
Předmět:	Mathematics - Combinatorics
Zdroj:	J. Graph Theory, 99(2):251-277, February 2022
Druh dokumentu:	Working Paper
DOI:	10.1002/jgt.22740
Popis:	A graph $G$ is $d$-degenerate if every non-null subgraph of $G$ has a vertex of degree at most $d$. We prove that every $n$-vertex planar graph has a $3$-degenerate induced subgraph of order at least $3n/4$. Comment: 28 pages, 12 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2002.07984 Zobrazit plný text záznamu View this record from Arxiv