Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree

Electronic Journal Of Combinatorics

François Dross¹ 

关键词: Graph theory;    Planar graphs;    Sparse graphs;    Vertex decompositions;    Independent sets;    Forests;   

DOI  :  

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

来源: Electronic Journal Of Combinatorics

【 摘 要 】

An $({\cal I},{\cal F}_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M<3$ and $d \ge \fr

【 授权许可】

Others