Graph Theory and Combinatorics Seminar

Title: DP vertex-arboricity of sparse graphs

Abstract: The vertex arboricity, $va(G)$, of a  multigraph $G$ is the minimum number $k$ for which the vertex set of $G$ can be partitioned into $k$ subsets, each of which induces a graph with no cycles.

By definition, if $va(G)= k$, then the chromatic number, $\chi(G)$, satisfies $k\leq \chi(G)\leq 2k$. Cornerstone  results of Borodin in 1976 and of Bollob\' as and Manvel in 1979 on a more general topic yield an analog for  vertex arboricity of the Gallai's lower bound on the number of edges in a $(2k-1)$-critical graph. 

In this talk we consider the DP-version of vertex arboricity. Introducing a slight generalization of this notion, we derive lower  bounds on the number of edges in graphs critical with respect to DP vertex arboricity better than Gallai's bound. The proof yields similar bounds  on  the number of edges in graphs critical w.r.t. vertex arboricity and w.r.t.  list arboricity.

This is joint work with P. Bradshaw and Z. Xiang