Size of edge-critical uniquely 3-colorable planar graphs

作者：Li, Zepeng^*; Zhu, Enqiang; Shao, Zehui; Xu, Jin

来源：Discrete Mathematics, 2016, 339(4): 1242-1250.

DOI：10.1016/j.disc.2015.11.009

• Planar graph
• Uniquely 3-colorable planar graph
• Edge-critical

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 is an element of 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 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 vertical bar E(G)vertical bar <= 5/2n - 6, which improves the upper bound 3/8n - 17/3 given by Matsumoto (Matsumoto, 2013). Furthermore, we find some edge-critical uniquely 3-colorable planar graphs with n(=10, 12, 14) vertices and 5/2n - 7 edges.

• 出版日期2016-4-6
• 单位成都大学; 北京大学