Planar graphs without mutually adjacent 3-, 5-, and 6-cycles are 3-degenerate (Q2144489)

A simple, finite, and undirected graph \(G\) is said to be \(k\)-degenerate if every subgraph of \(G\) has a vertex with degree at most \(k\). Two graphs are adjacent if they share at least one edge. Some known sufficient conditions for planar graphs to be 3-degenerate are as follows. \par 1.) Planar graphs without 3-cycles are 3-degenerate. \par 2.) Planar graphs without 5-cycles are 3-degenerate. \par 3.) Planar graphs without 6-cycles are 3-degenerate. \par 4.) Planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this article, the authors generalize the known results stated above. Let \(\mathcal{A}\) denote the family of planar graphs without mutually adjacent 3-, 5-, and 6-cycles. A graph \(G\) without mutually adjacent 3-, 5-, and 6-cycles means that \(G\) cannot contain three graphs, say \(G_1\), \(G_2\), and \(G_3\), where \(G_1\) is a 3-cycle, \(G_2\) is a 5-cycle, and \(G_3\) is a 6-cycle such that each pair of \(G_1\), \(G_2\), and \(G_3\) are adjacent. They prove that if \(G \in \mathcal{A}\), then \(G\) is 3-degenerate. As an immediate consequence, they have that every planar graph without mutually adjacent 3-, 5-, and 6-cycles is DP-4-colorable.