Tight bound on treedepth in terms of pathwidth and longest path

02/06/2023
by   Meike Hatzel, et al.
0

We show that every graph with pathwidth strictly less than a that contains no path on 2^b vertices as a subgraph has treedepth at most 10ab. The bound is best possible up to a constant factor.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset