Um algoritmo exato para biclique-coloração - Gomes, Guilherme de C. M.; dos Santos, Vinicius Fernandes (Anais do Encontro de Teoria da Computação (ETC), 2017)
O número biclique-cromático X 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 X B (G) para um grafo G é ∑ p 2 -completo para qualquer k ≥ 2. Nosso principal resultado neste trabalho é um algoritmo baseado em inclusão-exclusão de complexidade O*(2 n ) para se computar X B (G) de forma exata.