Size of edge-critical uniquely 3-colorable planar graphs

Original · EN

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. A uniquely k-colorable graph G is edge-critical if G-e is not a uniquely k-colorable graph for any edge e∈ E(G). Mel'nikov and Steinberg [L. S. Mel'nikov, R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977) 203-206] asked to find an exact upper bound for the number of edges in a edge-critical 3-colorable planar graph with n vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if G is such a graph with n(≥6) vertices, then |E(G)|≤ 5/2n-6, which improves the upper bound 8/3n-17/3 given by Matsumoto [N. Matsumoto, The size of edge-critical uniquely 3-colorable planar graphs, Electron. J. Combin. 20 (3) (2013) #P49]. Furthermore, we find some edge-critical 3-colorable planar graphs which have n(=10,12, 14) vertices and 5/2n-7 edges.