Note on (semi-)proper orientation of some triangulated planar graphs

作者：

Highlights：

• We discuss the semi-proper orientation number and the proper orientation number of some triangulated planar graphs.

• Semi-proper orientation number, which was first introduced by Dehghan and Havet in 2020, is based on proper orientation number.

• Proper orientation number was first introduced by Araújo, Cohen, Rezende, Havet and Moura in 2015.

• We attack the problem of proper orientation number proposed by Araújo, Cohen, Rezende, Havet and Moura in 2015 by proving tight upper bounds of the proper orientation number on triangulated grid and fish.

• We prove the tight lower bound of the semi-proper orientation number on iterated triangulation.

摘要

•We discuss the semi-proper orientation number and the proper orientation number of some triangulated planar graphs.•Semi-proper orientation number, which was first introduced by Dehghan and Havet in 2020, is based on proper orientation number.•Proper orientation number was first introduced by Araújo, Cohen, Rezende, Havet and Moura in 2015.•We attack the problem of proper orientation number proposed by Araújo, Cohen, Rezende, Havet and Moura in 2015 by proving tight upper bounds of the proper orientation number on triangulated grid and fish.•We prove the tight lower bound of the semi-proper orientation number on iterated triangulation.

论文关键词：Proper orientation number,Semi-proper orientation number,Triangulated planar graph

论文评审过程：Received 5 July 2020, Revised 30 September 2020, Accepted 3 October 2020, Available online 27 October 2020, Version of Record 27 October 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125723