29 citations · 212 across the 50 of their papers we have counts for
6 papers · 1 filter
Single-conflict colorings of degenerate graphs
Peter Bradshaw, Tomáš Masařík
We consider the single-conflict coloring problem, a graph coloring problem in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex color…
Tuza's Conjecture for Threshold Graphs
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik +4
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds…
Robust Connectivity of Graphs on Surfaces
Peter Bradshaw, Tomáš Masařík, Jana Novotná +1
Let denote the set of leaves in a tree . One natural problem is to look for a spanning tree of a given graph such that is as large as possible. This proble…
Constant congestion brambles in directed graphs
Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski +1
The Directed Grid Theorem, stating that there is a function such that a directed graphs of directed treewidth at least contains a directed grid of size at least as a…
Random 2-cell embeddings of multistars
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2
Random 2-cell embeddings of a given graph are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, , of s…
The Phase Transition of Discrepancy in Random Hypergraphs
Calum MacRury, Tomáš Masařík, Leilani Pai +1
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on vertices and edges. In the first (edge-independent)…