Autor(es)

Flavia Bonomo and Maria Chudnovsky and Peter Maceli and Oliver Schaudt and Maya Stein and Mingxian Zhong

URL Pública

Abstract

We present an algorithm to 3-colour an n-vertex graph G without triangles or induced paths on seven vertices in O (n7) time. This is a first step toward solving a problem of [18]; the complete solution appears in the companion paper, also submitted to this journal. Our algorithm can be extended to solve the list 3-colouring problem, where each vertex is assigned a subset of 11, 2, 3l as its admissible colours. The complexity for this second problem is again O (n7), and if G is bipartite, it improves to O (n4).