Um algoritmo exato para biclique-coloração
Resumo
O número biclique-cromático B(G) de um grafo G = (V; E) é o menor inteiro k tal que existe uma k-coloração dos vertices de G com a propriedade de que nenhuma biclique maximal de G seja monocromática. Trabalhos recentes provaram que o problema de se computar B(G) para um grafo G é 2p-completo para qualquer k 2. Nosso principal resultado neste trabalho é um algoritmo baseado em inclusão-exclusão de complexidade O (2n) para se computar B(G) de forma exata.