1 citations · 2 across the 18 of their papers we have counts for
17 papers · 1 filter
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…
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…
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…
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…