166 citations · 647 across the 62 of their papers we have counts for
9 papers · 1 filter
Testing first-order properties for subclasses of sparse graphs
Zdenek Dvorak, Daniel Kral, Robin Thomas
We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mend…
Deciding first order logic properties of matroids
Tomas Gavenciak, Daniel Kral, Sang-il Oum
Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order logic property can be deci…
Min-max relations for odd cycles in planar graphs
Daniel Kral, Jean-Sebastien Sereni, Ladislav Stacho
Let m(G) be the maximum number of vertex-disjoint odd cycles of a graph G and t(G) the minimum number of vertices whose removal makes G bipartite. We show that t(G)<=6m(G) if G is…
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Frantisek Kardos, Daniel Kral, Jan Volec
We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge-cuts of G such that each edge is in a randomly chosen cut with pr…
A new lower bound based on Gromov's method of selecting heavily covered points
Daniel Kral, Lukas Mach, Jean-Sebastien Sereni
Boros and Furedi (for d=2) and Barany (for abritrary d) proved that there exists a positive real number c_d such that for every set P of n points in R^d in general position, there…
Classes of graphs with small rank decompositions are chi-bounded
Zdenek Dvorak, Daniel Kral
A class of graphs G is chi-bounded if the chromatic number of graphs in G is bounded by a function of the clique number. We show that if a class G is chi-bounded,then every class o…