1 citations · 2 across the 18 of their papers we have counts for
24 papers
W[1]-Hardness of Upper Clique Transversal
J. Pascal Gollin, Pascal J. Gollin, Tesshu Hanaka +3
A clique transversal of a graph is a set of vertices intersecting every maximal clique. We prove that deciding whether a graph has an inclusion-wise minimal clique transversal of s…
Excluding paths and bicliques
Maria Chudnovsky, Julien Codsi, Matjaž Krnc +1
Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type…
Clique-width and induced topological minors
Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič +2
A is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique o…
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…
Tree decompositions whose trees are subgraphs: An application of Simon's factorization
Romain Bourneuf, Gwenaël Joret, Piotr Micek +2
We show that every connected graph has a tree decomposition indexed by a tree such that is a subgraph of and the width of the tree decomposition is bounded from abo…
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…
Conformality of Minimal Transversals of Maximal Cliques
Endre Boros, Vladimir Gurvich, Martin Milanič +2
Given a hypergraph , the dual hypergraph of is the hypergraph of all minimal transversals of . A hypergraph is conformal if it is the family of maximal cliques of a graph…
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of c…
Induced Minor Models. I. Structural Properties and Algorithmic Consequences
Nicolas Bousquet, Clément Dallard, Maël Dumas +4
A graph is said to be an induced minor of a graph if can be obtained from by a sequence of vertex deletions and edge contractions. Equivalently, is an induced m…
Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
Endre Boros, Vladimir Gurvich, Martin Milanič +1
Given a hypergraph , the dual hypergraph of is the hypergraph of all minimal transversals of . The dual hypergraph is always Sperner, that i…
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
Computing Tree Decompositions with Small Independence Number
Clément Dallard, Fedor V. Fomin, Petr A. Golovach +2
The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the mini…