Coloração equilibrada de grafos n-Star-Clique
Resumo
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.
Palavras-chave:
Coloração equilibrada, grafos unipolares
Referências
Bodlaender, H. L. and Fomin, F. V. (2005). Equitable colorings of bounded treewidth graphs. Theoretical Computer Science, 349(1):22 – 30. Graph Colorings.
Chen, B.-L., Ko, M.-T., and Lih, K.-W. (1996). Equitable and m-bounded coloring of split graphs. In Deza, M., Euler, R., and Manoussakis, I., editors, Combinatorics and Computer Science, pages 1–5, Berlin, Heidelberg. Springer Berlin Heidelberg.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.
de C. M. Gomes, G., Lima, C. V. G. C., and dos Santos, V. F. (2018). Parameterized complexity of equitable coloring. Discrete Mathematics and Theoretical Computer Science. Artigo aceito para publicacao.
Grotschel, M., Lov´asz, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. In Berge, C. and Chv´atal, V., editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325 – 356. North-Holland.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Sprin- ger US, Boston, MA.
McDiarmid, C. and Yolov, N. (2015). Recognition of unipolar and generalised split graphs. Algorithms, 8(1):46–59.
Chen, B.-L., Ko, M.-T., and Lih, K.-W. (1996). Equitable and m-bounded coloring of split graphs. In Deza, M., Euler, R., and Manoussakis, I., editors, Combinatorics and Computer Science, pages 1–5, Berlin, Heidelberg. Springer Berlin Heidelberg.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.
de C. M. Gomes, G., Lima, C. V. G. C., and dos Santos, V. F. (2018). Parameterized complexity of equitable coloring. Discrete Mathematics and Theoretical Computer Science. Artigo aceito para publicacao.
Grotschel, M., Lov´asz, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. In Berge, C. and Chv´atal, V., editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325 – 356. North-Holland.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Sprin- ger US, Boston, MA.
McDiarmid, C. and Yolov, N. (2015). Recognition of unipolar and generalised split graphs. Algorithms, 8(1):46–59.
Publicado
02/07/2019
Como Citar
GUEDES, Matheus; DOS SANTOS, Vinicius .
Coloração equilibrada de grafos n-Star-Clique. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2019.6393.
