
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

Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
read it

Random 2cell embeddings of multistars
By using permutation representations of maps, one obtains a bijection be...
read it

The Phase Transition of Discrepancy in Random Hypergraphs
Motivated by the BeckFiala conjecture, we study the discrepancy problem...
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

On Weak Flexibility in Planar Graphs
Recently, Dvořák, Norin, and Postle introduced flexibility as an extensi...
read it

Flexible List Colorings in Graphs with Special Degeneracy Conditions
For a given ε > 0, we say that a graph G is ϵflexibly kchoosable if th...
read it

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

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 Lcol...
read it

Optimal Discretization is Fixedparameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
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

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...
read it

Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
read it

FPT Algorithms for Diverse Collections of Hitting Sets
In this work, we study the dHitting Set and Feedback Vertex Set problem...
read it

Packing directed circuits quarterintegrally
The celebrated ErdősPósa theorem states that every undirected graph tha...
read it

Diversity in Combinatorial Optimization
When modeling an application of practical relevance as an instance of a ...
read it

Flexibility of planar graphs without 4cycles
Proper graph coloring assigns different colors to adjacent vertices of t...
read it

Flexibility of planar graphs of girth at least six
Let G be a planar graph with a list assignment L. Suppose a preferred co...
read it

Flexibility of trianglefree planar graphs
Let G be a planar graph with a list assignment L. Suppose a preferred co...
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

On difference graphs and the local dimension of posets
The dimension of a partiallyordered set (poset), introduced by Dushnik ...
read it

Parameterized Complexity of Fair Vertex Evaluation Problems
A prototypical graph problem is centered around a graph theoretic proper...
read it

Parameterized complexity of fair deletion problems II
Vertex deletion problems are those where given a graph G and a graph pro...
read it

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

Notes on complexity of packing coloring
A packing kcoloring for some integer k of a graph G=(V,E) is a mapping ...
read it

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
We study the Steiner Tree problem, in which a set of terminal vertices n...
read it
Tomáš Masařík
is this you? claim profile