166 citations · 647 across the 62 of their papers we have counts for
6 papers · 1 filter
Densities of 3-vertex graphs
Roman Glebov, Andrzej Grzesik, Ping Hu +3
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadru…
Graphic TSP in cubic graphs
Zdenek Dvorak, Daniel Kral, Bojan Mohar
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic…
Steinberg's Conjecture is false
Vincent Cohen-Addad, Michael Hebdige, Daniel Kral +2
Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.
Cyclic Coloring of Plane Graphs with Maximum Face Size 16 and 17
Zdenek Dvorak, Michael Hebdige, Filip Hlasek +2
Plummer and Toft conjectured in 1987 that the vertices of every 3-connected plane graph with maximum face size D can be colored using at most D+2 colors in such a way that no face…
Optimal-size clique transversals in chordal graphs
Jacob W. Cooper, Andrzej Grzesik, Daniel Kral
The following question was raised by Tuza in 1990 and Erdos et al. in 1992: if every edge of an n-vertex chordal graph G is contained in a clique of size at least four, does G have…
Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm
Zdenek Dvorak, Daniel Kral, Robin Thomas
We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmat…