Haven (graph theory)

In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs.[1] Their other applications include proving the existence of small separators on minor-closed families of graphs,[2] and characterizing the ends and clique minors of infinite graphs.[3][4]

  1. ^ Cite error: The named reference st93 was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference ast90 was invoked but never defined (see the help page).
  3. ^ Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), "Excluding infinite minors", Discrete Mathematics, 95 (1–3): 303–319, doi:10.1016/0012-365X(91)90343-Z, MR 1141945.
  4. ^ Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory, Series B, 87 (1): 197–206, doi:10.1016/S0095-8956(02)00034-5, MR 1967888.