research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
share
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
∙
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
∙
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
∙
10/22/2020
Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments ...
research
∙
06/05/2020
Clique-Width: Harnessing the Power of Atoms
Many NP-complete graph problems are polynomially solvable on graph class...
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
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
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
∙
02/15/2018
Duality Gap in Interval Linear Programming
This paper deals with the problem of linear programming with inexact dat...
research
∙
12/01/2017