PIMS- UVic Discrete Math Seminar: Sebastian Mies

  • Date: 01/12/2023
  • Time: 10:00
Sebastian Mies

University of Victoria


The Strong Nine Dragon Tree Conjecture for d <= k+1


The arboricity \Gamma(G) of an undirected graph G = (V,E) is the minimal number such that E can be partitioned into \Gamma(G) forests. Nash-Williams' formula states that \Gamma(G) = \ceil{ \gamma(G) }, where \gamma(G) is the maximum of |E_H|/(|V_H|-1) over all subgraphs (V_H, E_H) of G with |V_H| ≥ 2.


The Strong Nine Dragon Tree Conjecture states that if \gamma(G) ≤ k + d / (d+k+1) for natural numbers k, d, then there is a partition of the edge set of G into k+1 forests such that one forest has at most d edges in each connected component.


We settle the conjecture for d ≤ k + 1. For d ≤ 2(k+1), we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most d + \ceil{kd/(k+1)} - k edges.


As an application of this theorem, we show that every 5-edge-connected planar graph G has a 5/6-thin spanning tree, a spanning trees whose edges fill up at most 5/6 of every cut. This theorem is best possible, in the sense that we cannot replace 5-edge-connected with 4-edge-connected, even if we replace 5/6 with any positive real number less than 1. This strengthens a result of Merker and Postle which showed 6-edge-connected planar graphs have a 18/19-thin spanning tree.


This is joint work with Benjamin Moore.

Other Information: 

Time: 10am - 11am Pacific


Location: University of Victoria, COR A121


Registration: Free


More details listed here.