Zdeněk Dvořák

is this you? claim profile

0

  • On classes of graphs with strongly sublinear separators

    For real numbers c,epsilon>0, let G_c,epsilon denote the class of graphs G such that each subgraph H of G has a balanced separator of order at most c|V(H)|^1-epsilon. A class of graphs has strongly sublinear separators if it is a subclass of G_c,epsilon for some c,epsilon>0. We investigate properties of such graph classes, leading in particular to an approximate algorithm to determine membership in G_c,epsilon: there exist c'>0 such that for each input graph G, this algorithm in polynomial time determines either that G belongs to G_c',epsilon^2/160, or that G does not belong to G_c,epsilon.

    10/09/2017 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs

    A graph is k-degenerate if every subgraph has minimum degree at most k. We provide lower bounds on the size of a maximum induced 2-degenerate subgraph in a triangle-free planar graph. We denote the size of a maximum induced 2-degenerate subgraph of a graph G by α_2(G). We prove that if G is a connected triangle-free planar graph with n vertices and m edges, then α_2(G) ≥6n - m - 1/5. By Euler's Formula, this implies α_2(G) ≥4/5n. We also prove that if G is a triangle-free planar graph on n vertices with at most n_3 vertices of degree at most three, then α_2(G) ≥7/8n - 18 n_3.

    09/12/2017 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • On distance r-dominating and 2r-independent sets in sparse graphs

    Dvorak (2013) gave a bound on the minimum size of a distance r dominating set in the terms of the maximum size of a distance 2r independent set and generalized coloring numbers, thus obtaining a constant factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using an LP-based argument inspired by the work of Bansal and Umboh (2017).

    10/27/2017 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Least conflict choosability

    Given a multigraph, suppose that each vertex is given a local assignment of k colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least k for which this is always possible given any set of local assignments we call the conflict choosability of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that conflict choosability of simple graphs embeddable on a surface of Euler genus g is O(g^1/4 g) as g→∞. This is sharp up to the logarithmic factor.

    03/29/2018 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Structure and generation of crossing-critical graphs

    We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_3,3, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.

    03/05/2018 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Baker game and polynomial-time approximation schemes

    Baker devised a technique to obtain approximation schemes for many optimization problems restricted to planar graphs; her technique was later extended to more general graph classes. In particular, using the Baker's technique and the minor structure theorem, Dawar et al. gave Polynomial-Time Approximation Schemes (PTAS) for all monotone optimization problems expressible in the first-order logic when restricted to a proper minor-closed class of graphs. We define a Baker game formalizing the notion of repeated application of Baker's technique interspersed with vertex removal, prove that monotone optimization problems expressible in the first-order logic admit PTAS when restricted to graph classes in which the Baker game can be won in a constant number of rounds, and prove without use of the minor structure theorem that all proper minor-closed classes of graphs have this property.

    01/07/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Flexibility of triangle-free planar graphs

    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 four, then there exists an L-coloring respecting at least a constant fraction of the preferences.

    02/08/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Flexibility of planar graphs of girth at least six

    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 least three, then there exists an L-coloring respecting at least a constant fraction of the preferences.

    02/11/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 share

    read it

  • Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12

    We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c> 13 and d> 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c< 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c< 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c< 12.

    03/13/2019 ∙ by Drago Bokal, et al. ∙ 0 share

    read it