Complexity of equitable tree-coloring problems

arXiv1603.09070MaRDI QIDQ6272004FDOQ6272004

Kittikorn Nakprasit, Keaitsuda Nakprasit

Publication date: 30 March 2016

Abstract: 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 $qgeqp.$ 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.

This page was built for publication: Complexity of equitable tree-coloring problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6272004)