0xDE (11011110) wrote,

Grid minors in damaged grids

During my recent visit to UIUC, Tasos Sidiropoulos asked me a question about grid graphs that turns out to have a surprisingly clean answer. In rough terms, the question is: if an n × n square grid graph is damaged by the deletion of some number m of its vertices, how big a square grid must be left?

Read more...Collapse )
Tags: graph theory
  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment