Maximum 4-Degenerate Subgraph of a Planar Graph

Electronic Journal Of Combinatorics

Robert Lukot'¹ 

关键词: Degenerate subgraphs;    Planar graphs;    List colouring;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

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

【 授权许可】

Others