Open AccessColoração equilibrada de grafos n-Star-Clique
Author(s) -
Matheus R. Guedes,
Vanessa Cruz Santos
Publication year - 2019
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/etc.2019.6393
Subject(s) - combinatorics , clique , star (game theory) , mathematics , humanities , philosophy , mathematical analysis
Nesse artigo investigamos o problema de coloração equilibrada para grafos unipolares, uma superclasse de grafos split. Em particular, apresentamos um algoritmo baseado em fluxo máximo que soluciona esse problema em tempo polinomial, generalizando o resultado previamente conhecido para grafos split.