Premium
Marshals, monotone marshals, and hypertree‐width
Author(s) -
Adler Isolde
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20025
Subject(s) - hyperbolic tree , hypergraph , monotone polygon , mathematics , counterexample , combinatorics , treewidth , graph , discrete mathematics , pure mathematics , line graph , geometry , pathwidth , differential geometry , hyperbolic geometry
The tree‐width of a hypergraph H equals one less than the number of cops necessary to catch the robber in the Monotone Robber and Cops Game played on H . Analogously, the hypertree‐width of a hypergraph is characterised by the Monotone Robber and Marshals Game. While the Robber and Cops Game and its monotone variant coincide, Gottlob, Leone and Scarcello stated the corresponding question for the Robber and Marshals Game as an open problem. We give a negative answer. Concerning the generalised hypertree‐width, our counterexamples show that it is neither characterised by the Robber and Marshals Game nor by its monotone variant. We conclude by resuming how these hypergraph invariants are related. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 275–296 2004