Weak degeneracy of planar graphs without 4- and 6-cycles

DOI10.1016/J.DAM.2023.03.025zbMATH Open1512.05114arXiv2303.13267OpenAlexW4360882206MaRDI QIDQ6157423FDOQ6157423

Authors:

Publication date: 11 May 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A graph is $k$-degenerate if every subgraph $H$ has a vertex $v$ with $d_H(v)leqk$. The class of degenerate graphs plays an important role in the graph coloring theory. Observed that every $k$-degenerate graph is $(k+1)$-choosable and $(k+1)$-DP-colorable. Bernshteyn and Lee defined a generalization of $k$-degenerate graphs, which is called emph{weakly $k$-degenerate}. The weak degeneracy plus one is an upper bound for many graph coloring parameters, such as choice number, DP-chromatic number and DP-paint number. In this paper, we give two sufficient conditions for a plane graph without $4$- and $6$-cycles to be weakly $2$-degenerate, which implies that every such graph is $3$-DP-colorable and near-bipartite, where a graph is near-bipartite if its vertex set can be partitioned into an independent set and an acyclic set.

Full work available at URL: https://arxiv.org/abs/2303.13267

Recommendations

• \(G_2\)-manifolds from \(K3\) surfaces with non-symplectic automorphisms
• Counting associatives in compact $G_2$ orbifolds
• Constructions of compact \(G_2\)-holonomy manifolds
• \(K3\) surfaces with non-symplectic involution and compact irreducible \(G_{2}\)-manifolds
• Mini-workshop: Singularities in \(G_2\)-geometry. Abstracts from the mini-workshop held February 8--14, 2015.

zbMATH Keywords

weak degeneracydegenerate graphDP-coloringnear-bipartite

Mathematics Subject Classification ID

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

Cites Work

• Choosability and edge choosability of planar graphs without five cycles
• DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
• Planar graphs without cycles of specific lengths
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Planar graphs without normally adjacent short cycles
• DP-3-coloring of some planar graphs
• Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
• DP-4-colorability of planar graphs without adjacent cycles of given length
• Weak degeneracy of graphs
• DP-3-coloring of planar graphs without certain cycles
• Planar graphs without specific cycles are 2-degenerate
• Planar graphs without mutually adjacent 3-, 5-, and 6-cycles are 3-degenerate
• Cover and variable degeneracy

Cited In (10)

• Toroidal graphs without \(K_5^-\) and 6-cycles
• Counting associatives in compact $G_2$ orbifolds
• Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• \(G_2\)-manifolds from \(K3\) surfaces with non-symplectic automorphisms
• Planar graphs without 4-, 7-, 9-cycles and 5-cycles normally adjacent to 3-cycles
• Weak degeneracy of regular graphs
• Weak (2, 3)-decomposition of planar graphs
• Variable degeneracy of planar graphs without chorded 6-cycles
• Weak degeneracy of planar graphs and locally planar graphs

This page was built for publication: Weak degeneracy of planar graphs without 4- and 6-cycles

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