期刊
MATHEMATICS
卷 10, 期 15, 页码 -出版社
MDPI
DOI: 10.3390/math10152762
关键词
DP-coloring; list coloring; planar graph; cycle
类别
资金
- NSRF via the Program Management Unit for Human Resources and Institutional Development, Research and Innovation [B05F640106]
- National Research Council of Thailand (NRCT) [N41A640141]
In this paper, the authors extend previous studies on dynamic programming coloring and list coloring by considering different types of cycles and their adjacency relations. They present a theorem for every planar graph and provide a generalization of previous results.
In simple graphs, DP-coloring is a generalization of list coloring and thus many results of DP-coloring generalize those of list coloring. Xu and Wu proved that every planar graph without 5-cycles adjacent simultaneously to 3-cycles and 4-cycles is 4-choosable. Later, Sittitrai and Nakprasit showed that if a planar graph has no pairwise adjacent 3-, 4-, and 5-cycles, then it is DP-4-colorable, which is a generalization of the result of Xu and Wu. In this paper, we extend the results on 3-, 4-, 5-, and 6-cycles by showing that every planar graph without 6-cycles simultaneously adjacent to 3-cycles, 4-cycles, and 5-cycles is DP-4-colorable, which is also a generalization of previous studies as follows: every planar graph G is DP-4-colorable if G has no 6-cycles adjacent to i-cycles where i is an element of {3,4,5}.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据