1 citations · 2 across the 18 of their papers we have counts for
13 papers · 1 filter
Awesome graph parameters
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin +2
For a graph , we denote by the size of a maximum independent set and by the size of a maximum clique in . Our paper lies on the edge of two lines of research, r…
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…
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski
We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with…
On -Roman graphs: complexity of recognition and the case of split graphs
Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández +4
For a positive integer , a -Roman dominating function of a graph is a function satisfying $\sum_{u\in N(v)} f(u) \geq…
Sandwich Monotonicity and Recognition of Weighted Graph Classes
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +5
Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from…
Perfect phylogenies via the Minimum Uncovering Branching problem: efficiently solvable cases
Narmina Baghirova, Esther Galby, Martin Milanič
In this paper, we present new efficiently solvable cases of the Minimum Uncovering Branching problem, an optimization problem with applications in cancer genomics introduced by Huj…
Layered tree-independence number and clique-based separators
Clément Dallard, Martin Milanič, Andrea Munaro +1
Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublin…
Excluding an induced wheel minor in graphs without large induced stars
Mujin Choi, Claire Hilaire, Martin Milanič +1
We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer and any planar graph , the class of all $K_…
Treewidth versus clique number. V. Further connections with tree-independence number
Claire Hilaire, Martin Milanič, Đorđe Vasić
We continue the study of -bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation…
Linear colorings of graphs
Claire Hilaire, Matjaž Krnc, Martin Milanič +1
Motivated by algorithmic applications, Kun, O'Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two p…
Path Eccentricity and Forbidden Induced Subgraphs
Sylwia Cichacz, Claire Hilaire, Tomáš Masařík +2
The path eccentricity of a connected graph is the minimum integer such that has a path such that every vertex is at distance at most from the path. A result of Duff…
Tree independence number V. Walls and claws
Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2
Given a family of graphs, we say that a graph is -free if no induced subgraph of is isomorphic to a member of . Let be t…
Young domination on Hamming rectangles
Janko Gravner, Matjaž Krnc, Martin Milanič +1
We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolati…