
Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edgedisjo...
read it

Robust Connectivity of Graphs on Surfaces
Let Λ(T) denote the set of leaves in a tree T. One natural problem is to...
read it

Note on 3Coloring of (2P_4,C_5)Free Graphs
We show that the 3coloring problem is polynomialtime solvable on (2P_4...
read it

Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments ...
read it

CliqueWidth: Harnessing the Power of Atoms
Many NPcomplete graph problems are polynomially solvable on graph class...
read it

UBubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Interval graphs, intersection graphs of segments on a real line (interva...
read it

Subexponentialtime algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
read it

Colouring (P_r+P_s)Free Graphs
The kColouring problem is to decide if the vertices of a graph can be c...
read it

Duality Gap in Interval Linear Programming
This paper deals with the problem of linear programming with inexact dat...
read it

On the Simultaneous Minimum Spanning Trees Problem
Simultaneous Embedding with Fixed Edges (SEFE) is a problem where given ...
read it
Jana Novotná
is this you? claim profile