On the complexity of local-equitable coloring of graphs

An equitable k partition (k >= 2) of a vertex set S is a partition of S into k disjoint subsets (may be empty sets) such that the sizes of any two subsets of S differ by at most one. A local equitable k coloring of G is an assignment of k colors to the vertices of G such that, for every maximal clique of G, the coloring of this clique forms an equitable k-partition of itself. The local-equitable coloring of G is a stronger version of clique-coloring of graphs. Chordal graphs are 2-clique-colorable but not necessarily local-equitably 2-colorable. In this paper, we prove that it is NP-complete to decide the local-equitable 2-colorability in chordal graphs and even in split graphs. In addition, we prove that claw-free split graphs are local-equitably k-colorable when k <= 4, but not necessarily local-equitably k-colorable when k >= 5. A sufficient and sharp condition of local-equitably k-colorability is also given in claw-free split graphs. Secondly, we show that, given a split graph G, deciding the localequitable k-colorability of G is solvable in polynomial time when k = omega(G) - 1, where omega(G) is the clique number of G. At last, we prove that the decision problem of local-equitable 2-coloring of planar graphs is solvable in polynomial time. (C) 2022 Elsevier B.V. All rights reserved.