Abstract

A class F{\cal F} of graphs is called {\em tame} if there exists a constant kk so that every graph in F{\cal F} on nn vertices contains at most O(nk)O(n^k) minimal separators, {\em strongly-quasi-tame} if every graph in F{\cal F} on nn vertices contains at most O(nklog⁡n)O(n^{k \log n}) minimal separators, and {\em feral} if there exists a constant c>1c > 1 so that F{\cal F} contains nn-vertex graphs with at least cnc^n minimal separators for arbitrarily large nn. 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 kk-{\em creature}. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class F{\cal F} that excludes kk-creatures for some fixed constant kk is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class F{\cal F} is strongly quasi-tame if it excludes kk-creatures for some fixed constant kk and additionally every minimal separator can be dominated by another fixed constant k′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 kk-creatures and additionally excludes all cycles of length at least cc, for some constant cc, are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. {\bf (iii)} We show that every hereditary class that excludes kk-creatures and additionally excludes a complete graph on cc vertices for some fixed constant cc is tame.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.