5 citations · 8 across the 9 of their papers we have counts for
23 papers
Tree decompositions with bounded independence number: beyond independent sets
Martin Milanič, Paweł Rzążewski
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-in…
Allocation of Indivisible Items with Individual Preference Graphs
Nina Chiarelli, Clément Dallard, Andreas Darmann +5
This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference…
Complexity and algorithms for constant diameter augmentation problems
Eun Jung Kim, Martin Milanic, Jérôme Monnot +1
We study the following problem: for given integers and graph , can we obtain a graph with diameter via at most edge deletions ? We determine the computational comp…
On the degree sequences of dual graphs on surfaces
Endre Boros, Vladimir Gurvich, Martin Milanič +1
Given two graphs and with a one-to-one correspondence between their edges, when do and form a pair of dual graphs realizing the vertices and countries of a map…
Strong cliques in diamond-free graphs
Nina Chiarelli, Berenice Martínez Barona, Martin Milanič +2
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques…
Avoidable Vertices and Edges in Graphs
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich +2
A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as \te…