A note on uniquely 3-colourable planar graphs. Issue 5 (4th May 2017)

• Record Type: Journal Article
• Authors: Li, Zepeng; Zhu, Enqiang; Shao, Zehui; Xu, Jin
• Is Part Of: International journal of computer mathematics. Volume 94:Issue 5(2017)
• Page Start: 1028
• Page End: 1035
• Publication Date: 2017-05-04
• Subjects: Planar graph -- unique colouring -- uniquely 3-colourable planar graph -- construction; 05C15 -- 05C76; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2016.1167196
• Languages: English
• ISSNs: 0020-7160

Abstract

ABSTRACT: A graph G is uniquely k -colourable if the chromatic number of G is k and G has only one k -colouring up to permutation of the colours. Aksionov [ On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graph G has at most 4 triangles then G has two adjacent triangles. Furthermore, for anyk ≥ 5, we construct a uniquely 3-colourable planar graph with k triangles and without adjacent triangles.