标题： 公平树着色问题的复杂性 显示英文标题

标题： Complexity of equitable tree-coloring problems

摘要： A $(q,t)$\emph{树着色} of a graph $G$ is a $q$-coloring of vertices of $G$ such that the subgraph induced by each color class is a forest of maximum degree at most $t.$ A $(q,\infty)$\emph{树着色} of a graph $G$ is a $q$-coloring of vertices of $G$ such that the subgraph induced by each color class is a forest. 吴、张和李引入了\emph{公平$(q, t)$-树着色}（分别，\emph{公平$(q, \infty)$-树-coloring}）的概念，这是一种$(q,t)$-树着色（分别，$(q, \infty)$-树着色），使得任何两个颜色类的大小相差不超过一。 除其他结果外，他们得到了一个尖锐的上界，即最小的$p$使得 $K_{n,n}$对于每个$q\geq p.$都有一个公平的$(q, 1)$-树着色。 在本文中，我们得到一个多项式时间准则来判断完全二部图是否有一个公平的$(q,t)$-树着色或一个公平的$(q,\infty)$-树着色。 尽管如此，决定一个图$G$在一般情况下是否具有公平的$(q,t)$-树着色或公平的$(q,\infty)$-树着色是NP完全的。 显示英文摘要

摘要： A $(q,t)$\emph{-tree-coloring} of a graph $G$ is a $q$-coloring of vertices of $G$ such that the subgraph induced by each color class is a forest of maximum degree at most $t.$ A $(q,\infty)$\emph{-tree-coloring} of a graph $G$ is a $q$-coloring of vertices of $G$ such that the subgraph induced by each color class is a forest. Wu, Zhang, and Li introduced the concept of \emph{equitable $(q, t)$-tree-coloring} (respectively, \emph{equitable $(q, \infty)$-tree-coloring}) which is a $(q,t)$-tree-coloring (respectively, $(q, \infty)$-tree-coloring) such that the sizes of any two color classes differ by at most one. Among other results, they obtained a sharp upper bound on the minimum $p$ such that $K_{n,n}$ has an equitable $(q, 1)$-tree-coloring for every $q\geq p.$ In this paper, we obtain a polynomial time criterion to decide if a complete bipartite graph has an equitable $(q,t)$-tree-coloring or an equitable $(q,\infty)$-tree-coloring. Nevertheless, deciding if a graph $G$ in general has an equitable $(q,t)$-tree-coloring or an equitable $(q,\infty)$-tree-coloring is NP-complete.