Equitable Partition of Graphs into Independent Sets and Cliques

• Bruno Monteiro UFMG
• Vinicius dos Santos UFMG

DOI: https://doi.org/10.5753/etc.2019.6392

Resumo

A graph is (k, l) if its vertex set can be partitioned into k independent sets and l cliques. Deciding if a graph is (k, l) can be seen as a generalization of coloring, since deciding is a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable. A coloring is equitable if the cardinalities of the color classes differ by at most 1. In this paper, we generalize both the (k, l) and the equitable coloring problems, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and l cliques is solvable in polynomial time if max(k, l) 2, and NP complete otherwise.

Palavras-chave: Equitable Partition, Graphs, Independent Sets and Cliques

Referências

Brandst¨adt, A. (1984). Partitions of graphs into one or two independent sets and cliques. Technical report, Forschungsergebnisse der Friedrich-Schiller-Universitat¨at Jena.

Brandst¨adt, A. (1996). Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics, 152(1-3):47–54.

Brandst¨adt, A. (1998). Corrigendum. Discrete Math., 186:295.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity ofcom- puter computations, pages 85–103. Springer.