66 citations · 323 across the 55 of their papers we have counts for
7 papers · 1 filter
A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Martin Milanič, Nevena Pivač
A minimal separator in a graph is an inclusion-minimal set of vertices that separates some fixed pair of nonadjacent vertices. A graph class is said to be tame if there exists a po…
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +3
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called the simultaneous interval number. This parameter is related to the simultane…
On balanceable and simply balanceable regular graphs
Milad Ahanjideh, Martin Milanič, Mary Servatius
We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs such that any -coloring of the edges of a sufficiently large complete…
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Clément Dallard, Matjaž Krnc, O-joung Kwon +4
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes de…
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
We consider the task of allocating indivisible items to agents, when the agents' preferences over the items are identical. The preferences are captured by means of a directed acycl…