Meike Hatzel ; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge - Constant Congestion Brambles

dmtcs:6699 - Discrete Mathematics & Theoretical Computer Science, March 31, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.6699
Constant Congestion BramblesArticle

Authors: Meike Hatzel ORCID; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge

    A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H1 and H2 in the bramble either V(H1)V(H2) or there is an edge of G with one endpoint in V(H1) and the second endpoint in V(H2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n1/2+δ) requires size exponential in Ω(n2δ) for any fixed δ(0,12]. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order ˜Ω(k1/2) and size ˜O(k3/2). (˜Ω and ˜O hide polylogarithmic factors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order ˜Ω(k1/2) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ(0,12], every graph G of treewidth at least k contains a bramble of order ˜Ω(k1/2+δ) and size 2˜O(k2δ).


    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: March 31, 2022
    Accepted on: February 9, 2022
    Submitted on: August 6, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704
    • Structure Theory for Directed Graphs; Funder: European Commission; Code: 648527

    Consultation statistics

    This page has been seen 979 times.
    This article's PDF has been downloaded 898 times.