Papers for
database indexing teams
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Upper bound on minimum vertices blocking complete cliques in hypergraphs
Isolation of $k$-cliques in uniform hypergraphs
Abstract: A copy of a hypergraph $F$ is called an $F$-copy. For any integers $k$ and $r$ with $2 \leq r \leq k$, let $K_k^r$ denote the complete $r$-uniform hypergraph whose vertex set is $[k] = \{1, 2, \dots, k\}$ (that is, the edges of $K_k^r$ are the $r$-element subsets of $[k]$). Given an $r$-uniform $m$-edge hypergraph $H$, the $K_k^r$-isolation number of $H$, denoted by $ι(H, K_k^r)$, is the size of a smallest subset $D$ of the vertex set of $H$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $K_k^r$-copies contained by $H$ (equivalently, $H-N[D]$ contains no $K_k^r$-copy). We prove that if $H$ is connected and not a $K_k^r$-copy, then $$ι(H, K^r_k) \le \left \lfloor \frac{(r-1)m + 1}{(r-1)(\binom{k}{r}+1) + 1} \right \rfloor.$$ The bound is best possible. This is a solution to a problem of Li, Zhang and Ye. We also provide an alternative proof for $r < k$. Both proofs introduce new ideas for establishing bounds on isolation parameters.
Induced packing branchwidth links graph structures and decompositions
Induced packing treewidth III. Branch decompositions
Abstract: The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.