Browsing Bergen Open Research Archive by Author "Thomasse, Stephan"
Now showing items 1-2 of 2
-
Subdivisions in digraphs of large out-degree or large dichromatic number
Aboulker, Pierre; Cohen, Nathann; Havet, Frederic; Lochet, William; Moura, Phablo F S; Thomasse, Stephan (Journal article; Peer reviewed, 2019)In 1985, Mader conjectured the existence of a function f such that every digraph with minimum out-degree at least f ( k ) contains a subdivision of the transitive tournament of order k . This conjecture is still completely ... -
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems
Fomin, Fedor; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomasse, Stephan; Zehavi, Meirav (Peer reviewed; Journal article, 2019)We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For ...