@inbook{68577da67fa642bd8528b5537f6bdbde,

title = "Four colouring the vertices of the triangulation of a polygon containing a hole",

abstract = "A simple linear-time algorithm is presented for four-colouring the vertices of a triangulation of a polygon containing a single hole. The algorithm consists of reducing a triangulation by the removal of both polygon and hole ear vertices, if any, followed by the removal of colour-isolated vertices until a 3-coloured tessellation remains. The triangulation is then re-built, using at most four colours. The paper concludes by recognising the similarity between the colouring of triangulations of polygons containing a hole and the colouring of bipartite and permutation graphs. {\textcopyright} Springer-Verlag 2003.",

author = "Seed, {Graham M.} and Clark, {D. E R} and Raffaella Ocone and Yang, {Xiaoyan Y.}",

year = "2003",

doi = "10.1007/3-540-44842-X_91",

language = "English",

isbn = "978-3-540-40156-8",

volume = "2669",

series = "Lecture Notes in Computer Science",

pages = "894--902",

booktitle = "Computational Science and Its Applications — ICCSA 2003",

}