Grid Minors in Damaged Grids

Electronic Journal Of Combinatorics

David Eppstein¹ 

关键词: graph theory;    grid graphs;    graph minors;    subgraphs;    shallow minors;    treewidth;    vertex deletion;   

DOI  :  

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

来源: Electronic Journal Of Combinatorics

【 摘 要 】

We prove upper and lower bounds on the size of the largest square grid graph that is a subgraph, minor, or shallow minor of a graph in the form of a larger square grid from which a specified number of vertices have been deleted. Our bounds are tight to wi

【 授权许可】

Others