The size of edge-critical uniquely 3-colorable planar graphs (Q396890)

Summary: 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\in E(G)\). In this paper, we prove that if \(G\) is an edge-critical uniquely 3-colorable planar graph, then \(|E(G)|\leq \frac{8}{3}|V(G)|-\frac{17}{3}\). On the other hand, there exists an infinite family of edge-critical uniquely 3-colorable planar graphs with \(n\) vertices and \(\frac{9}{4}n-6\) edges. Our result gives a first non-trivial upper bound for \(|E(G)|\).