Constructions of uniquely 3-colorable graphs

Constructing the graphs with some specific properties is an important and interesting problem in the field of graph theory. A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k-coloring up to permutation of the colors. In this paper, we give three methods for recursively constructing uniquely 3-colorable graphs. Moreover, we give a simple counterexample on 16 vertices to S J Xu's conjecture concerning uniquely 3-colorable graphs without triangles, and based on this graph we construct an infinite family of uniquely 3-colorable, 4-regular and triangle-free graphs by our construction methods.National 973 Program of China [2013CB329600]; National Natural Science Foundation of China [61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437]CPCI-S(ISTP)143-14