18 papers
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…
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…
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…
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…
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…