8 papers
Conflict-Free Coloring Planar Graphs with 4 Colors
Petr HlinÄný, Petr Hliněný, Lukáš Málik +1
We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every vertex v has a nei…
Measuring Depth of Matroids
Jakub Balabán, Petr HlinÄný, Jan Jedelský +1
Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursiv…
A Unified FPT Framework for Crossing Number Problems
Ãric Colin de Verdière, Petr HlinÄný
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified fr…
Crossing Number is NP-hard for Constant Path-width (and Tree-width)
Petr HlinÄný, Liana Khazaliya
The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem,…
On the Uncrossed Number of Graphs
Martin Balko, Petr HlinÄný, Tomáš MasaÅÃk +3
Visualizing a graph in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, MasaÅÃk and HlinÄný [GD 2023] recent…
Transductions of Graph Classes Admitting Product Structure
Petr HlinÄný, Jan Jedelský
In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for gr…