| Full text | |
| Author(s): |
Rojas Anriquez, Alberto
;
Stein, Maya
Total Authors: 2
|
| Document type: | Journal article |
| Source: | ALGORITHMICA; v. N/A, p. 23-pg., 2022-10-17. |
| Abstract | |
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) | |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |