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

Zepeng Li, Naoki Matsumoto, Enqiang Zhu, Jin Xu and Tommy Jensen
Additional contact information
Zepeng Li: School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China
Naoki Matsumoto: Research Institute for Digital Media and Content, Keio University, Tokyo 108-8345, Japan
Enqiang Zhu: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Jin Xu: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Tommy Jensen: Department of Mathematics, Kyungpook National University, Daegu 41566, Korea

Mathematics, 2019, vol. 7, issue 9, 1-6

Abstract: 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 ≤ 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 ≠ j . One of our constructions implies that there exists an infinite family of edge-critical uniquely three-colorable plane graphs with n vertices and 7 3 n - 14 3 edges, where n ( ≥ 11 ) is odd and n ≡ 2 ( mod 3 ) .

Keywords: plane graph; unique coloring; uniquely three-colorable plane graph; construction; adjacent ( i , j )-faces (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/9/793/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/9/793/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:9:p:793-:d:262847

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().