29 citations · 212 across the 50 of their papers we have counts for
7 papers · 1 filter
On Weak Flexibility in Planar Graphs
Bernard Lidický, Tomáš Masařík, Kyle Murphy +1
Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs [JGT 19']. In this new setting, each vertex in some subset of has a…
Flexible List Colorings in Graphs with Special Degeneracy Conditions
Peter Bradshaw, Tomáš Masařík, Ladislav Stacho
For a given , we say that a graph is -flexibly -choosable if the following holds: for any assignment of color lists of size on ,…
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná +2
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph…
Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four
Ilkyoo Choi, Felix Christian Clemen, Michael Ferrara +3
A graph where each vertex has a list of available colors is -colorable if there is a proper coloring such that the color of is in for each . A graph is…
Optimal Discretization is Fixed-parameter Tractable
Stefan Kratsch, Tomáš Masařík, Irene Muzi +2
Given two disjoint sets and of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separ…
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
Radek Hušek, Dušan Knop, Tomáš Masařík
In the Steiner Tree problem we are given an edge weighted undirected graph and a set of terminals . The task is to find a connected subgraph of conta…
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Jan Kratochvíl, Tomáš Masařík, Jana Novotná
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, the…