# PIMS- UVic Discrete Math Seminar: Sebastian Mies

## Topic

## Speakers

## Details

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.

## Additional Information

**Time**: 10am - 11am Pacific

**Location**: University of Victoria, COR A121

**Registration**: Free

More details listed here.

Sebastian Mies

**Scientific, Seminar**

**January 12, 2023**

**-**