On Uniquely 3-Colorable Plane Graphs without Adjacent Faces of Prescribed Degrees

Mathematics

Tommy Jensen¹  Enqiang Zhu²  Naoki Matsumoto³  Jin Xu⁴  Zepeng Li⁵ 

[1] Department of Mathematics, Kyungpook National University, Daegu 41566, Korea;Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China;Research Institute for Digital Media and Content, Keio University, Tokyo 108-8345, Japan;School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China;

关键词: plane graph;    unique coloring;    uniquely three-colorable plane graph;    construction;    adjacent (i,j)-faces;   

DOI  :  10.3390/math7090793

来源: DOAJ

【 摘 要 】

A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k-coloring up to the permutation of the colors. For a plane graph G, two faces $f_1$ and $f_2$ of G are adjacent $(i,j)$-faces if $d(f_1)=i$, $d(f_2)=j$, and $f_1$ and $f_2$ have a common edge, where $d(f)$ is the degree of a face f. In this paper, we prove that every uniquely three-colorable plane graph has adjacent $(3,k)$-faces, where $k\le 5$. The bound of five for k is the best possible. Furthermore, we prove that there exists a class of uniquely three-colorable plane graphs having neither adjacent $(3,i)$-faces nor adjacent $(3,j)$-faces, where $i,j$ are fixed in $\{3,4,5\}$ and $i\ne j$. One of our constructions implies that there exists an infinite family of edge-critical uniquely three-colorable plane graphs with n vertices and $\frac{7}{3}n-\frac{14}{3}$ edges, where $n(\ge 11)$ is odd and $n\equiv 2(\mathrm{mod}3)$.

【 授权许可】

Unknown