2020/07/17 by Gartland, Peter, Lokshtanov, Daniel
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2007.08761
A class \cal F of graphs is called \em tame if there exists a constant k so that every graph in \cal F on n vertices contains at most O(nk) minimal separators, \em strongly-quasi-tame if every graph in \cal F on n vertices contains at most O(nk log n) minimal separators, and \em feral if there exists a constant c > 1 so that \cal F contains n-vertex graphs with at least cn minimal separators for arbitrarily large n. 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 k-\em creature. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class \cal F that excludes k-creatures for some fixed constant k is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class \cal F is strongly quasi-tame if it excludes k-creatures for some fixed constant k and additionally every minimal separator can be dominated by another fixed constant k' 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 k-creatures and additionally excludes all cycles of length at least c, for some constant c, are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. \bf (iii) We show that every hereditary class that excludes k-creatures and additionally excludes a complete graph on c vertices for some fixed constant c is tame.