A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1-Spernerhypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding 1-Sperner hypergraphs.These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of 1-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.
COBISS.SI-ID: 1541798340
A graph class is said to be tame if graphs in the class have a polynomially bounded number of minimal separators. Tame graph classes have good algorithmic properties, which follow, for example, from an algorithmic metatheorem of Fomin, Todinca, and Villanger from 2015. We show that a hereditary graph class X is tame if and only if the subclass consisting of graphs in X without clique cutsets is tame. This result and Ramsey's theorem lead to several types of sufficient conditions for a graph class to be tame. In particular, we show that any hereditary class of graphs of bounded clique cover number that excludes some complete prism is tame, where a complete prism is the Cartesian product of a complete graph with a K_2. We apply these results, combined with constructions of graphs with exponentially many minimal separators, to develop a dichotomy theorem separating tame from non-tame graph classes within the family of graph classes defined by sets of forbidden induced subgraphs with at most four vertices.
COBISS.SI-ID: 57192963
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call (tw, ?)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is (tw, ?)-bounded. Our results imply that the class of 1-perfectly orientable graphs is (tw, ?)-bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic implications of (tw, ?)-boundedness related to list k-coloring and clique problems.
COBISS.SI-ID: 36187651