7 papers · 1 filter
Tree-independence number of -free graphs with no large bicliques
Václav Blažej, J. Pascal Gollin, Tomáš Hons +5
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bo…
Tree-independence number and forbidden induced subgraphs: excluding a -vertex path and a -biclique
Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2
We show that for every positive integer there exists an integer such that every graph that contains no induced subgraph isomorphic to either the -vertex path or…
Graph Classes Closed under Self-intersection
Konrad K. Dabrowski, Vadim V. Lozin, Martin Milanič +3
A graph class is monotone if it is closed under taking subgraphs. It is known that a monotone class defined by finitely many obstructions has bounded treewidth if and only if one o…
Closing paths to cycles in symmetric graphs
Martin Milanič, Đorđe Mitrović
It was shown by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2022 that every induced -edge path in a vertex-transitive graph closes to an induced cycle. Similar resu…
Treewidth versus clique number: induced minors
Claire Hilaire, Martin Milanič, Nicolas Trotignon +1
We prove that a hereditary class of graphs is -bounded if and only if the induced minors of the graphs from the class form a -bounded class.
The Upper Clique Transversal Problem: Hardness and Algorithms
Martin Milanič, Yushi Uno
A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable…
On minimally tough chordal graphs
Clément Dallard, Blas Fernández, Gyula Y. Katona +2
Katona and Varga showed that for any rational number , no chordal graph is minimally -tough, while Katona and Khan characterized all minimally -tough, chordal…