Abstract
A class of graphs is called {\em tame} if there exists a constant so that every graph in on vertices contains at most minimal separators, {\em strongly-quasi-tame} if every graph in on vertices contains at most minimal separators, and {\em feral} if there exists a constant so that contains -vertex graphs with at least minimal separators for arbitrarily large . The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention. A key graph-theoretic object in the quest for such a classification is the notion of a -{\em creature}. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class that excludes -creatures for some fixed constant is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class is strongly quasi-tame if it excludes -creatures for some fixed constant and additionally every minimal separator can be dominated by another fixed constant number of vertices. The tools developed also lead to a number of additional results of independent interest. {\bf (i) We obtain a complete classification of all hereditary graph classes defined by a finite set of forbidden induced subgraphs into strongly quasi-tame or feral. This generalizes Milanič and Pivač [WG'19]. {\bf (ii)} We show that hereditary class that excludes -creatures and additionally excludes all cycles of length at least , for some constant , are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. {\bf (iii)} We show that every hereditary class that excludes -creatures and additionally excludes a complete graph on vertices for some fixed constant is tame.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.