Construction of acyclically 4-colourable planar triangulations with minimum degree 4. Issue 9 (2nd September 2019)

• Record Type: Journal Article
• Authors: Zhu, Enqiang; Li, Zepeng; Shao, Zehui; Xu, Jin
• Is Part Of: International journal of computer mathematics. Volume 96:Issue 9(2019)
• Page Start: 1723
• Page End: 1734
• Publication Date: 2019-09-02
• Subjects: Acyclic 4-colouring -- triangulations -- diamond -- operations -- odd-vertex; 05C05 -- 05C40 -- 05C69; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2018.1476684
• Languages: English
• ISSNs: 0020-7160

Abstract

ABSTRACT: An acyclic colouring of a graph is a proper colouring of the graph, for which every cycle uses at least three colours. In this paper, we describe a method for constructing all 4-connected acyclically 4-colourable planar triangulations that have exactly four odd-vertices, except the ones that contain no adjacent odd-vertices. Unlike previous operations, our method successfully establishes a connection with (acyclic) 4-colourings. Moreover, we discuss a special class of graphs, called diamond triangulations, and give a necessary and sufficient condition for a diamond triangulation to be acyclically 4-colourable.