research
∙
07/12/2023
Group Fairness in Social Choice
We consider a voting model, where a number of candidates need to be sele...
share
research
∙
06/15/2023
Minimizing an Uncrossed Collection of Drawings
In this paper, we introduce the following new concept in graph drawing. ...
research
∙
05/25/2023
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
We show that the Maximum Weight Independent Set problem (MWIS) can be so...
research
∙
11/02/2022
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
A random 2-cell embedding of a connected graph G in some orientable surf...
research
∙
09/13/2022
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P_4
An oriented graph is a digraph that does not contain a directed cycle of...
research
∙
08/31/2022
On weighted graph separation problems and flow-augmentation
One of the first application of the recently introduced technique of flo...
research
∙
07/15/2022
A tight quasi-polynomial bound for Global Label Min-Cut
We study a generalization of the classic Global Min-Cut problem, called ...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
03/09/2022
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
We revisit recent developments for the Maximum Weight Independent Set pr...
research
∙
02/25/2022
List Locally Surjective Homomorphisms in Hereditary Graph Classes
A locally surjective homomorphism from a graph G to a graph H is an edge...
research
∙
12/12/2021
Single-conflict colorings of degenerate graphs
We consider single-conflict colorings, a variant of graph colorings in w...
research
∙
08/11/2021
Linear Bounds for Cycle-free Saturation Games
Given a family of graphs ℱ, we define the ℱ-saturation game as follows. ...
research
∙
05/20/2021
Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjo...
research
∙
04/24/2021
Robust Connectivity of Graphs on Surfaces
Let Λ(T) denote the set of leaves in a tree T. One natural problem is to...
research
∙
03/15/2021
Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
research
∙
03/08/2021
Random 2-cell embeddings of multistars
By using permutation representations of maps, one obtains a bijection be...
research
∙
02/15/2021
The Phase Transition of Discrepancy in Random Hypergraphs
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem...
research
∙
11/12/2020
Note on 3-Coloring of (2P_4,C_5)-Free Graphs
We show that the 3-coloring problem is polynomial-time solvable on (2P_4...
research
∙
09/16/2020
On Weak Flexibility in Planar Graphs
Recently, Dvořák, Norin, and Postle introduced flexibility as an extensi...
research
∙
06/29/2020
Flexible List Colorings in Graphs with Special Degeneracy Conditions
For a given ε > 0, we say that a graph G is ϵ-flexibly k-choosable if th...
research
∙
06/05/2020
Clique-Width: Harnessing the Power of Atoms
Many NP-complete graph problems are polynomially solvable on graph class...
research
∙
04/23/2020
Flexibility of Planar Graphs – Sharpening the Tools to Get Lists of Size Four
A graph where each vertex v has a list L(v) of available colors is L-col...
research
∙
03/05/2020
Optimal Discretization is Fixed-parameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
research
∙
02/19/2020
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Interval graphs, intersection graphs of segments on a real line (interva...
research
∙
02/10/2020
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
In the Steiner Tree problem we are given an edge weighted undirected gra...
research
∙
12/03/2019
Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
research
∙
11/12/2019
FPT Algorithms for Diverse Collections of Hitting Sets
In this work, we study the d-Hitting Set and Feedback Vertex Set problem...
research
∙
07/04/2019
Packing directed circuits quarter-integrally
The celebrated Erdős-Pósa theorem states that every undirected graph tha...
research
∙
03/18/2019
Diversity in Combinatorial Optimization
When modeling an application of practical relevance as an instance of a ...
research
∙
03/04/2019
Flexibility of planar graphs without 4-cycles
Proper graph coloring assigns different colors to adjacent vertices of t...
research
∙
02/11/2019
Flexibility of planar graphs of girth at least six
Let G be a planar graph with a list assignment L. Suppose a preferred co...
research
∙
02/08/2019
Flexibility of triangle-free planar graphs
Let G be a planar graph with a list assignment L. Suppose a preferred co...
research
∙
04/30/2018
Colouring (P_r+P_s)-Free Graphs
The k-Colouring problem is to decide if the vertices of a graph can be c...
research
∙
03/23/2018
On difference graphs and the local dimension of posets
The dimension of a partially-ordered set (poset), introduced by Dushnik ...
research
∙
03/19/2018
Parameterized Complexity of Fair Vertex Evaluation Problems
A prototypical graph problem is centered around a graph theoretic proper...
research
∙
03/19/2018
Parameterized complexity of fair deletion problems II
Vertex deletion problems are those where given a graph G and a graph pro...
research
∙
02/15/2018
Duality Gap in Interval Linear Programming
This paper deals with the problem of linear programming with inexact dat...
research
∙
12/22/2017
Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping ...
research
∙
10/02/2017