Xin Zhang (张欣), On equitable tree-colorings of graphs

An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$, denoted by $v{a}_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k^{\prime }$-coloring for some $k^{\prime }>k$. For example, the complete bipartite graph $K_{9,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely, it is the minimum integer $k$ such that $G$ has an equitable tree-$k^{\prime }$-coloring for any integer $k^{\prime }\ge k$, and is denoted by $v{a}_{eq}^{\ast }(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu, X. Zhang and H. Li in 2013. In 2016, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings, one of which, for example, conjectures that every graph with maximum degree at most $\mathrm{\Delta }$ is equitably tree-$k$-colorable for any integer $k\ge (\mathrm{\Delta }+1)/2$, i.e, $v{a}_{eq}^{\ast }(G)\le \lceil (\mathrm{\Delta }+1)/2\rceil$. In this talk, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms, and also share some interesting problems for further research.