3 papers
math.CO2026
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…
math.CO2025
General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
Gaspard Charvy, Tomáš Masařík
We investigate a very recent concept for visualizing various aspects of a graph in the plane using a collection of drawings introduced by Hliněný and Masařík [GD 2023]. Formally, g…
math.CO2023
Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen +1
A graph contains a graph as an induced minor if can be obtained from after vertex deletions and edge contractions. We show that for every -vertex planar graph $H…