
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 cV(H)^1epsilon. 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 ∙ shareread it

Induced 2degenerate Subgraphs of Trianglefree Planar Graphs
A graph is kdegenerate if every subgraph has minimum degree at most k. We provide lower bounds on the size of a maximum induced 2degenerate subgraph in a trianglefree planar graph. We denote the size of a maximum induced 2degenerate subgraph of a graph G by α_2(G). We prove that if G is a connected trianglefree 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 trianglefree 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 ∙ shareread it

On distance rdominating and 2rindependent 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 LPbased argument inspired by the work of Bansal and Umboh (2017).
10/27/2017 ∙ by Zdeněk Dvořák, et al. ∙ 0 ∙ shareread 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 ∙ shareread it

Structure and generation of crossingcritical graphs
We study ccrossingcritical graphs, which are the minimal graphs that require at least c edgecrossings when drawn in the plane. For c=1 there are only two such graphs without degree2 vertices, K_5 and K_3,3, but for any fixed c>1 there exist infinitely many ccrossingcritical graphs. It has been previously shown that ccrossingcritical graphs have bounded pathwidth 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 crossingcritical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded pathwidth. Then we show that every ccrossingcritical graph can be obtained from a ccrossingcritical graph of bounded size by replicating boundedsize parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the ccrossingcritical 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 ∙ shareread it

Baker game and polynomialtime 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 PolynomialTime Approximation Schemes (PTAS) for all monotone optimization problems expressible in the firstorder logic when restricted to a proper minorclosed 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 firstorder 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 minorclosed classes of graphs have this property.
01/07/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 ∙ shareread it

Flexibility of trianglefree 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 trianglefree and all lists have size at least four, then there exists an Lcoloring respecting at least a constant fraction of the preferences.
02/08/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 ∙ shareread 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 Lcoloring respecting at least a constant fraction of the preferences.
02/11/2019 ∙ by Zdeněk Dvořák, et al. ∙ 0 ∙ shareread it

Bounded maximum degree conjecture holds precisely for ccrossingcritical graphs with c ≤ 12
We study ccrossingcritical graphs, which are the minimal graphs that require at least c edgecrossings when drawn in the plane. For every fixed pair of integers with c> 13 and d> 1, we give first explicit constructions of ccrossingcritical 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 ccrossingcritical graph with c< 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of ccrossingcritical 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 ∙ shareread it
Zdeněk Dvořák
is this you? claim profile