12 papers
An ErdÅs-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
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…
Minimal toughness in subclasses of weakly chordal graphs
J. Pascal Gollin, Martin MilaniÄ, Laura Ogrin
The toughness of a graph is defined as the largest real number such that for any set such that is disconnected, has at least times more elem…
On -Roman graphs: complexity of recognition and the case of split graphs
Kenny BeÅ¡ter Å torgel, Kenny Bešter Štorgel, Nina Chiarelli +7
For a positive integer , a -Roman dominating function of a graph is a function satisfying $\sum_{u\in N(v)} f(u) \geq…
Dominated balanced separators in wheel-induced-minor-free graphs
Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc +1
Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every…