Xin Zhang (张欣) gave a talk on the problem of partitioning a graph into forests of the almost equal size at the Discrete Math Seminar

On February 25, 2020, Xin Zhang (张欣) from Xidian University, China gave a talk on the problem of equitable tree-k-coloring of graphs and its variations. The title of his talk is “On the equitable tree-coloring of graphs with low degeneracy“. He is currently visiting the IBS discrete mathematics group for 1 year until August 2020 for his sabbatical leave.

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.

Welcome Xin Zhang from Xidian University, a new visiting scholar in the IBS discrete mathematics group

Xin Zhang

The IBS discrete mathematics group welcomes Prof. Xin Zhang (张欣), a new visiting scholar from Xidian University, China. He is visiting the IBS discrete mathematics group for one year from August 22, 2019.

He received his Ph.D. from Shandong University in China and is currently an associate professor in the School of Mathematics and Statistics, Xidian University, Xi’an, China.


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 $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>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’$-coloring for any integer $k’\geq k$, and is denoted by $va_{eq}^*(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 $\Delta$ is equitably tree-$k$-colorable for any integer $k\geq (\Delta+1)/2$, i.e, $va_{eq}^*(G)\leq \lceil(\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.

Xin Zhang presented many results on equitable tree-k-colorings of graphs at the discrete math seminar

On May 16, 2019, Xin Zhang (张欣) from Xidian University, China discusses various results on the equitable tree-k-coloring of graphs, a problem of partitioning the vertex set of a graph into vertex-disjoint induced subgraphs having no cycles with almost same size. The title of his talk was “On equitable tree-colorings of graphs”. Xin Zhang is visiting IBS Discrete Mathematics Group from May 15 to May 19.