On graphs with a simple structure of maximal cliques
By: J. Pascal Gollin, Meike Hatzel, Sebastian Wiederrecht
Potential Business Impact:
Simplifies complex network problems for computers.
We say that a hereditary graph class $\mathcal{G}$ is \emph{clique-sparse} if there is a constant $k=k(\mathcal{G})$ such that for every graph $G\in\mathcal{G}$, every vertex of $G$ belongs to at most $k$ maximal cliques, and any maximal clique of $G$ can be intersected in at most $k$ different ways by other maximal cliques. We provide various characterisations of clique-sparse graph classes, including a list of five parametric forbidden induced subgraphs. We show that recent techniques for proving induced analogues of Menger's Theorem and the Grid Theorem of Robertson and Seymour can be lifted to prove induced variants in clique-sparse graph classes when replacing ``treewidth'' by ''tree-independence number''.
Similar Papers
Every Graph is Essential to Large Treewidth
Combinatorics
Finds hidden patterns in complex networks.
First-order transducibility among classes of sparse graphs
Logic in Computer Science
Makes computers understand complex shapes better.
Burling graphs in graphs with large chromatic number
Combinatorics
Finds hidden patterns to color graphs faster.