109
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

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

, , &
Pages 1723-1734 | Received 14 Dec 2014, Accepted 08 May 2018, Published online: 31 May 2018
 

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.

2010 AMS SUBJECT CLASSIFICATIONS:

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.