Equitable Partition of Graphs into Independent Sets and Cliques
Bruno de S. Monteiro, Vinícius Fernandes dos Santos · Matemática Contemporânea · 2022
A graph is (k, ℓ) if its vertex set can be partitioned into k independent sets and l cliques.Deciding if a graph is (k, ℓ) can be seen as a generalization of coloring, since deciding if a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable.A coloring is equitable if the cardinalities of color classes differ by at most 1.In this paper, we generalize the equitable coloring problem, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and ℓ cliques is solvable in polynomial time if max(k, ℓ) ≤ 2, and NP-complete otherwise.