Size of edge-critical uniquely 3-colorable planar graphs

详细信息    查看全文

• 作者：Zepeng Li^a ; ^{lizepeng@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Enqiang Zhu^a ; ^{zhuenqiang@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Zehui Shao^b ; ^c ; ^{zshao@cdu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Jin Xu^a ; ^{jxu@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Planar graph ; Uniquely 3-colorable planar graph ; Edge-critical
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1242-1250
• 全文大小：454 K

文摘

A graph G$G$ is uniquely k-colorable   if the chromatic number of G$G$ is 4c03" title="Click to view the MathML source">k$k$ and G$G$ has only one 4c03" title="Click to view the MathML source">k$k$-coloring up to permutation of the colors. A uniquely 4c03" title="Click to view the MathML source">k$k$-colorable graph G$G$ is edge-critical   if G−e$G-e$ is not a uniquely 4c03" title="Click to view the MathML source">k$k$-colorable graph for any edge c05e0e2cbff9a12d9c8a0301cf1415b8" title="Click to view the MathML source">e∈E(G)$e\in E\left(G\right)$. 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$n$ vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if G$G$ is such a graph with 749ca130999bee0778fe" title="Click to view the MathML source">n(≥6)$n(\ge 6)$ vertices, then $\left|E\left(G\right)\right|\le \frac{5}{2}n-6$, which improves the upper bound 7430d79ef30ef705ca495b">$\frac{8}{3}n-\frac{17}{3}$ 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 $\frac{5}{2}n-7$ edges.