Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy

A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla, J.-L. Wu, and X. Zhang (2011), who proved that any graph with maximum degree at most $\Delta$ has a $\Delta$-coloring so that each color class induces a graph with maximum degree at most 1. After that, many results on this topic were published in the literature. For example, L. Esperet, L. Lemoine, and F. Maffray (2015) showed that any planar graph admits an equitable tree-$k$-coloring for every integer $k\ge 4$，and G. Chen, Y. Gao, S. Shan, G. Wang, and J.-L. Wu (2017) proved that any 5-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every $k\geq \lceil\frac{\Delta+1}{2}\rceil$.

In this talk, we review part of the known results and the conjectures on the equitable tree-coloring of graphs, and then show the sketch proofs of our three new results as follows:

(a) the vertex set of any graph $G$ can be equitably partitioned into $k$ subsets for any integer $k\geq\max\{\lceil\frac{\Delta(G)+1}{2}\rceil,\lceil\frac{|G|}{4}\rceil\}$ so that each of them induces a linear forest;

(b) any plane graph with independent crossings admits an equitable tree-$k$-coloring for every integer $k\ge 8$;

(c) any $d$-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every integer $k\geq (\Delta+1)/2$ provided that $\Delta\geq 10d$.

This is a joint work with Yuping Gao, Bi Li, Yan Li, and Bei Niu.