research
∙
08/31/2023
Dually conformal hypergraphs
Given a hypergraph ℋ, the dual hypergraph of ℋ is the hypergraph of all ...
share
research
∙
08/18/2023
Fair Allocation Algorithms for Indivisible Items under Structured Conflict Constraints
We consider the fair allocation of indivisible items to several agents w...
research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
01/23/2023
Functionality of box intersection graphs
Functionality is a graph complexity measure that extends a variety of pa...
research
∙
12/16/2022
Computing Well-Covered Vector Spaces of Graphs using Modular Decomposition
A graph is well-covered if all its maximal independent sets have the sam...
research
∙
10/01/2022
Conditions for minimally tough graphs
Katona, Soltész, and Varga showed that no induced subgraph can be exclud...
research
∙
09/25/2022
Tree decompositions with bounded independence number: beyond independent sets
We continue the study of graph classes in which the treewidth can only b...
research
∙
08/26/2022
Avoidability beyond paths
The concept of avoidable paths in graphs was introduced by Beisegel, Chu...
research
∙
07/20/2022
Computing Tree Decompositions with Small Independence Number
The independence number of a tree decomposition is the maximum of the in...
research
∙
06/30/2022
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
We continue the study of (tw,ω)-bounded graph classes, that is, heredita...
research
∙
02/09/2022
Allocation of Indivisible Items with Individual Preference Graphs
This paper studies the allocation of indivisible items to agents, when e...
research
∙
11/08/2021
Tree decompositions with bounded independence number and their algorithmic applications
In 2020, Dallard, Milanič, and Štorgel initiated a systematic study of g...
research
∙
06/18/2021
Graphs with at most two moplexes
A moplex is a natural graph structure that arises when lifting Dirac's c...
research
∙
08/03/2020
Shifting paths to avoidable ones
An extension of an induced path P in a graph G is an induced path P' suc...
research
∙
08/02/2020
On the degree sequences of dual graphs on surfaces
Given two graphs G and G^* with a one-to-one correspondence between thei...
research
∙
06/10/2020
Treewidth versus clique number in graph classes with a forbidden structure
Treewidth is an important graph invariant, relevant for both structural ...
research
∙
03/25/2020
Fair packing of independent sets
In this work we add a graph theoretical perspective to a classical probl...
research
∙
07/28/2019
Avoidable Vertices and Edges in Graphs
A vertex in a graph is simplicial if its neighborhood forms a clique. We...
research
∙
12/13/2018
Mind the Independence Gap
The independence gap of a graph was introduced by Ekim et al. (2018) as ...
research
∙
12/13/2018
A characterization of claw-free CIS graphs and new results on the order of CIS graphs
A graph is CIS if every maximal clique interesects every maximal stable ...
research
∙
08/24/2018
Detecting strong cliques
A strong clique in a graph is a clique intersecting every maximal indepe...
research
∙
08/03/2018
Searching for square-complementary graphs: non-existence results and complexity of recognition
A graph is square-complementary (squco, for short) if its square and com...
research
∙
05/12/2018
Bipartite Graphs of Small Readability
We study a parameter of bipartite graphs called readability, introduced ...
research
∙
05/09/2018
Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
A hypergraph H is said to be 1-Sperner if for every two hyperedges the s...
research
∙
03/12/2018
New Algorithms for Weighted k-Domination and Total k-Domination Problems in Proper Interval Graphs
Given a positive integer k, a k-dominating set in a graph G is a set of ...
research
∙
08/15/2017
Almost Well-Covered Graphs Without Short Cycles
We study graphs in which the maximum and the minimum sizes of a maximal ...
research
∙
06/25/2017