On purely tree-colorable planar graphs

•We study the purely tree-4-colorable planar graphs.•By constructing an infinite family of purely tree-colorable 4-connected maximal planar graphs, We disprove Xu's conjecture [16].•We propose a conjecture to characterize the structure of purely tree-colorable 4-connected maximal planar graphs.

A tree-k-coloring of a graph G is a k-coloring of G such that the subgraph induced by the union of any two color classes is a tree. G is purely tree-k-colorable if the chromatic number of G is k and any k-coloring of G is a tree-k-coloring. Xu [16] conjectured that there exist only two purely tree-4-colorable 4-connected maximal planar graphs. In this paper, we construct an infinite family of purely tree-colorable 4-connected maximal planar graphs, called dumbbell-maximal planar graphs, which disprove Xu's conjecture. Moreover, we give the enumeration of dumbbell-maximal planar graphs and propose a conjecture on such graphs. It turns out that the conjecture implies naturally the uniquely 4-colorable planar graph conjecture.