论文标题
没有某些周期的平面图的DP-3色彩
DP-3-coloring of planar graphs without certain cycles
论文作者
论文摘要
DP颜色是列表着色的概括，该列表是由Dvočhk和Postle引入的[J. [J.组合。理论ser。 B 129（2018）38--54]。张[信息。过程。 Lett。 113（9）（2013）354--356]表明，每个平面图都不相邻三角形，也不是5-，6-，9个循环3-偶然。刘等。 [离散数学。 342（2019）178--189]表明，每个没有4-，5-，6和9个周期的平面图都是可dp-3的。在本文中，我们表明每个平面图都不具有相邻三角形，也不是5-，6-，9个周期的dp-3可选，这概括了这些结果。 Yu等。通过表明（i）具有至少三角形距离的每个平面图，给出了三个波尔多类型的结果，至少三角形和无4-，5个循环是DP-3上色的； （ii）每个平面图至少两个和无4-，5-，6个周期的距离dp-3可选； （iii）每个平面图至少两个和5个，6-，7个周期的三角形距离都是可dp-3的。在最后一节中，我们还给出了两个波尔多型的结果：（i）每个平面图在距离小于两个的5-，6-，8个循环和三角形都不是DP-3上色的； （ii）每个平面图在距离小于两个的距离时都不是4-，5-，7个骑士和三角形的图形。
DP-coloring is a generalization of list coloring, which was introduced by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018) 38--54]. Zhang [Inform. Process. Lett. 113 (9) (2013) 354--356] showed that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is 3-choosable. Liu et al. [Discrete Math. 342 (2019) 178--189] showed that every planar graph without 4-, 5-, 6- and 9-cycles is DP-3-colorable. In this paper, we show that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is DP-3-colorable, which generalizes these results. Yu et al. gave three Bordeaux-type results by showing that (i) every planar graph with the distance of triangles at least three and no 4-, 5-cycles is DP-3-colorable; (ii) every planar graph with the distance of triangles at least two and no 4-, 5-, 6-cycles is DP-3-colorable; (iii) every planar graph with the distance of triangles at least two and no 5-, 6-, 7-cycles is DP-3-colorable. We also give two Bordeaux-type results in the last section: (i) every plane graph with neither 5-, 6-, 8-cycles nor triangles at distance less than two is DP-3-colorable; (ii) every plane graph with neither 4-, 5-, 7-cycles nor triangles at distance less than two is DP-3-colorable.
