29 citations · 212 across the 50 of their papers we have counts for
18 papers · 1 filter
Path Eccentricity and Forbidden Induced Subgraphs
Sylwia Cichacz, Claire Hilaire, Tomáš Masařík +2
The path eccentricity of a connected graph is the minimum integer such that has a path such that every vertex is at distance at most from the path. A result of Duff…
Proper Rainbow Saturation Numbers for Cycles
Anastasia Halfpap, Bernard Lidický, Tomáš Masařík
We say that an edge-coloring of a graph is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of receive the same color. Further…
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2
A random 2-cell embedding of a connected graph in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of fa…
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of
Linda Cook, Tomáš Masařík, Marcin Pilipczuk +2
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph is -free if does not contain as an induced sub(di)graph. The…
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)…
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 ,…
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
Flexibility of planar graphs without 4-cycles
Tomáš Masařík
Proper graph coloring assigns different colors to adjacent vertices of the graph. Usually, the number of colors is fixed or as small as possible. Consider applications (e.g. varian…
Flexibility of planar graphs of girth at least six
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at…
Flexibility of triangle-free planar graphs
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G is triangle-free and all lists have size at least…
On difference graphs and the local dimension of posets
Jinha Kim, Ryan R. Martin, Tomáš Masařík +4
The dimension of a partially-ordered set (poset), introduced by Dushnik and Miller (1941), has been studied extensively in the literature. Recently, Ueckerdt (2016) proposed a vari…
Triangle-free planar graphs with the smallest independence number
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n+1)/3, and described an infinite class of tight examples. We sho…