2020/03/09 by Niu, Bei, Li, Bi, Zhang, Xin
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.03945
An equitable tree-k-coloring of a graph is a vertex k-coloring such that each color class induces a forest and the size of any two color classes differ by at most one. In this work, we show that every interval graph G has an equitable tree-k-coloring for any integer k≥ \lceil(Δ(G)+1)/2\rceil, solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree-k-coloring for a given integer k. For disjoint union of split graphs, or K1,r-free interval graphs with r≥ 4, we prove that it is W[1]-hard to decide whether there is an equitable tree-k-coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively.