| Texto completo | |
| Autor(es): |
Rojas Anriquez, Alberto
;
Stein, Maya
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMICA; v. N/A, p. 23-pg., 2022-10-17. |
| Resumo | |
For any odd t >= 9, we present a polynomial-time algorithm that solves the 3-colouring problem, and finds a 3-colouring if one exists, in Pt-free graphs of odd girth at least t-2. In particular, our algorithm works for (P9, C3, C5)-free graphs, thus making progress towards determining the complexity of 3-colouring in P-t-free graphs, which is open for t >= 8. (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |