Planar graphs without specific cycles are 2-degenerate |
| |
Authors: | Patcharapan Jumnongnit Wannapol Pimpasalee |
| |
Institution: | 1. School of Science, University of Phayao, Phayao, 56000, Thailand;2. Department of Science and Mathematics, Faculty of Science and Health Technology, Kalasin University, Kalasin, 46000, Thailand |
| |
Abstract: | A graph G is k-degenerate if each subgraph of G has a vertex of degree at most k. It is known that every simple planar graph with girth 6, or equivalently without 3-, 4-, and 5-cycles, is 2-degenerate. In this work, we investigate for which k every planar graph without 4-, 6-, … , and 2k-cycles is 2-degenerate. We determine that k is 5 and the result is tight since the truncated dodecahedral graph is a 3-regular planar graph without 4-, 6-, and 8-cycles. As a related result, we also show that every planar graph without 4-, 6-, 9-, and 10-cycles is 2-degenerate. |
| |
Keywords: | 2-degenerate graph Planar graph 3-choosability Forbidden cycle |
本文献已被 ScienceDirect 等数据库收录! |
|