Size of edge-critical uniquely 3-colorable planar graphs

A graph GG is uniquely k-colorable   if the chromatic number of GG is kk and GG has only one kk-coloring up to permutation of the colors. A uniquely kk-colorable graph GG is edge-critical   if G−eG−e is not a uniquely kk-colorable graph for any edge e∈E(G)e∈E(G). Mel’nikov and Steinberg (Mel’nikov and Steinberg, 1977) asked to find an exact upper bound for the number of edges in an edge-critical uniquely 3-colorable planar graph with nn vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if GG is such a graph with n(≥6)n(≥6) vertices, then |E(G)|≤52n−6, which improves the upper bound 83n−173 given by Matsumoto (Matsumoto, 2013). Furthermore, we find some edge-critical uniquely 3-colorable planar graphs with n(=10,12,14)n(=10,12,14) vertices and 52n−7 edges.