20 citations · 35 across the 18 of their papers we have counts for
18 papers
On Borodin-Kostochka conjecture for correspondence coloring
Zdeněk Dvořák, Ross J. Kang, David Mikšaník
Borodin and Kostochka in 1977 conjectured that if a graph has maximum degree and its clique number satisfies , then its chromatic number satisfies $…
Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio
Marthe Bonamy, Zdeněk Dvořák, Lukas Michel +1
We give an exact characterization of monotone graph classes C with bounded average degree that satisfy the following property: The domination number of every graph from C is bounde…
Open problems of the 33rd Workshop on Cycles and Colourings
János Barát, Zdeněk Dvořák, Penny Haxell +6
Since its beginnings, every Cycles and Colourings workshop holds one or two open problem sessions; this document contains the problems (together with notes regarding the current st…
Improved Decomposition Bounds for Partition Polytopes and Odd-Covers
Steffen Borgwardt, Zdeněk Dvořák, Bryce Frederickson +2
The assignments of a set of items into clusters of prescribed sizes can be encoded as the vertices of the partition polytope . W…
On a conjecture concerning 4-coloring of graphs with one crossing
Zdeněk Dvořák, Bernard Lidický, Bojan Mohar
We conjecture that every graph of minimum degree five with no separating triangles and drawn in the plane with one crossing is 4-colorable. In this paper, we use computer enumerati…
Lollipops, dense cycles and chords
Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé +1
In 1980, Gupta, Kahn and Robertson proved that every graph with minimum degree at least contains a cycle containing at least vertices each having at least $…
Flow-critical graphs
Arnbjörg Soffía Árnadóttir, Zdeněk Dvořák, Bernard Lidický +3
Lovász et al. proved that every -edge-connected graph has a nowhere-zero -flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $3…
Sparsity of 3-flow critical graphs
Zdeněk Dvořák, Sergey Norin
A connected graph G is 3-flow-critical if G does not have a nowhere-zero 3-flow, but every proper contraction of G does. We prove that every n-vertex 3-flow-critical graph other th…
Clustered coloring of (path+2K_1)-free graphs on surfaces
Zdeněk Dvořák
Esperet and Joret proved that planar graphs with bounded maximum degree are 3-colorable with bounded clustering. Liu and Wood asked whether the conclusion holds with the assumption…
Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs
Zdeněk Dvořák, Daniel Lokshtanov, Fahad Panolan +3
We investigate a fundamental vertex-deletion problem called (Induced) Subgraph Hitting: given a graph and a set of forbidden graphs, the goal is to compute a mini…
On density of -flow-critical graphs
Zdeněk Dvořák, Bojan Mohar
For an abelian group , a graph is said to be -flow-critical if does not admit a nowhere-zero -flow, but for each edge , the contraction has a nowh…
Independence number in triangle-free graphs avoiding a minor
Zdeněk Dvořák, Liana Yepremyan
The celebrated Hadwiger's conjecture states that if a graph contains no minor then it is -colourable. If true, it would in particular imply that every -vertex $K_{t…
Graphs avoiding immersion of K_{3,3}
Zdeněk Dvořák, Michal Hruška
DeVos and Malekian gave a structural description of graphs avoiding an immersion of K_{3,3}, showing that all such graphs are composed over small edge-cuts from graphs with at most…
1-subdivisions, fractional chromatic number and Hall ratio
Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu
The Hall ratio of a graph G is the maximum of |V(H)|/alpha(H) over all subgraphs H of G. Clearly, the Hall ratio of a graph is a lower bound for the fractional chromatic number. It…
A -choosable graph that is not -choosable
Zdeněk Dvořák, Xiaolan Hu, Jean-Sébastien Sereni
In 1980, Erdős, Rubin and Taylor asked whether for all positive integers , , and , every -choosable graph is also -choosable. We provide a negative answer…
Islands in minor-closed classes. I. Bounded treewidth and separators
Zdeněk Dvořák, Sergey Norin
The clustered chromatic number of a graph class is the minimum integer such that for some the vertices of every graph in the class can be colored in colors so that ever…
Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable
Zdeněk Dvořák, Ken-ichi Kawarabayashi
We prove that every triangle-free graph of tree-width t has chromatic number at most ceil((t + 3)/2), and demonstrate that this bound is tight. The argument also establishes a conn…
A simplified discharging proof of Grötzsch theorem
Zdeněk Dvořák
In this note, we combine ideas of several previous proofs in order to obtain a quite short proof of Grötzsch theorem.