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

DOI10.1016/J.DISC.2022.112942MaRDI QIDQ2144489zbMATH OpenOpenAlexFDO

Authors Pongpat Sittitrai, Kittikorn Nakprasit

Publication date 14 June 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2022.112942

zbMATH Keywords

3-degenerate graphsdischarging methodplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38)

Review text

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.

Recommendations

• Planar graphs without specific cycles are 2-degenerate
• Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
• Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
• scientific article; zbMATH DE number 5914884
• Planar graphs without cycles of specific lengths

Cites work

• A sufficient condition for DP-4-colorability
• Choosability and edge choosability of planar graphs without five cycles
• DP-4-colorability of planar graphs without adjacent cycles of given length
• DP-4-colorability of two classes of planar graphs
• Planar graphs without cycles of specific lengths

Cited in

(8)

• Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
• Planar graphs without specific cycles are 2-degenerate
• Vertex 2-arboricity of planar graphs without 4-cycles adjacent to 6-cycles
• Weak degeneracy of planar graphs without 4- and 6-cycles
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• List recoloring of planar graphs
• Planar graphs with distance of 3-cycles at least 2 and no cycles of lengths 5, 6, 7
• Degeneracy of toroidal graphs without special cycles

This page was built for publication: Planar graphs without mutually adjacent 3-, 5-, and 6-cycles are 3-degenerate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144489)