Planar graphs without mutually adjacent 3-, 5-, and 6-cycles are 3-degenerate |
| |
Affiliation: | Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand |
| |
Abstract: | A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say , and , where is a 3-cycle, is a 5-cycle, and is a 6-cycle such that each pair of , and are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable. |
| |
Keywords: | Planar graph 3-degenerate Discharging method |
本文献已被 ScienceDirect 等数据库收录! |
|