3-Colouring graphs without triangles or induced paths on seven vertices
2014, arXiv preprint arXiv:1410.0040, 2014Citas: 8
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Oliver Schaudt and Maya Stein
URL Pública
https://www.dim.uchile.cl/~mstein/P7free-v6.pdfAbstract
We present an algorithm to 3-colour a graph G without triangles or induced paths on seven vertices in O (| V (G)| 7) time. In fact, our algorithm solves the list 3-colouring problem, where each vertex is assigned a subset of {1, 2, 3} as its admissible colours.