| Article ID: | iaor20125368 |
| Volume: | 64 |
| Issue: | 3 |
| Start Page Number: | 384 |
| End Page Number: | 399 |
| Publication Date: | Nov 2012 |
| Journal: | Algorithmica |
| Authors: | Stacho Juraj |
| Keywords: | graph coloring |
Determining the complexity of the colouring problem on AT‐free graphs is one of long‐standing open problems in algorithmic graph theory. One of the reasons behind this is that AT‐free graphs are not necessarily perfect unlike many popular subclasses of AT‐free graphs such as interval graphs or co‐comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3‐colouring problem on AT‐free graphs.