Construction of acyclically 4-colourable planar triangulations with minimum degree 4

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.

KEYWORDS:

• Acyclic 4-colouring
• triangulations
• diamond
• operations
• odd-vertex

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C05
• 05C40
• 05C69

Acknowledgements

The authors are very much indebted to the referees for their valuable comments and suggestions which greatly improved the original manuscript of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is supported by National Natural Science Foundation of China (No. 61632002, 61672051, 61702075) and China Postdoctoral Science Foundation under Grant 2017M611223. 61632002, 61672051, 61702075