2016/03/30 by Keaitsuda Maneeruk Nakprasit, Nakprasit, Keaitsuda Maneeruk, Kittikorn Nakprasit +1
Computer Science · Decision Sciences · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1603.09070
openalex publication_date 2016/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A (q,t)-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,∞)-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 equitable (q, t)-tree-coloring (respectively, equitable (q, ∞)-tree-coloring) which is a (q,t)-tree-coloring (respectively, (q, ∞)-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 Kn,n has an equitable (q, 1)-tree-coloring for every q≥ 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,∞)-tree-coloring. Nevertheless, deciding if a graph G in general has an equitable (q,t)-tree-coloring or an equitable (q,∞)-tree-coloring is NP-complete.