A note on uniquely 3-colourable planar graphs

doi:10.1080/00207160.2016.1167196

CORC > 北京大学 > 信息科学技术学院

	A note on uniquely 3-colourable planar graphs
	Li, Zepeng ; Zhu, Enqiang ; Shao, Zehui ; Xu, Jin
刊名	INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
	2017
关键词	Planar graph unique colouring uniquely 3-colourable planar graph construction SIZE
DOI	10.1080/00207160.2016.1167196
英文摘要	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 counter example 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 any k > 5, we construct a uniquely 3-colourable planar graph with k triangles and without adjacent triangles.; State Key Development Program of Basic Research of China (973) [2013CB329600]; National Natural Science Foundation of China [61372191, 61309015, 61572492]; China Postdoctoral Science Foundation [2014M560851]; SCI(E); ARTICLE; 5; 1028-1035; 94
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/476238]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Li, Zepeng,Zhu, Enqiang,Shao, Zehui,et al. A note on uniquely 3-colourable planar graphs[J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS,2017.
APA	Li, Zepeng,Zhu, Enqiang,Shao, Zehui,&Xu, Jin.(2017).A note on uniquely 3-colourable planar graphs.INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS.
MLA	Li, Zepeng,et al."A note on uniquely 3-colourable planar graphs".INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS (2017).