2021/12/17 by Qianqian Wang, Tao Wang, Wang, Qianqian +3
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2112.09334
openalex publication_date 2021/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Bernshteyn and Lee defined a new notion, weak degeneracy, which is slightly weaker than the ordinary degeneracy. It is proved that strictly f-degenerate transversal is a common generalization of list coloring, L-forested-coloring and DP-coloring. In this paper, we consider three classes of graphs, including planar graphs without any configuration in Fig. 2, toroidal graphs without any configuration in Fig. 5, and planar graphs without intersecting 5-cycles. We give structural results for each class of graphs, and prove each structure is reducible for weakly 3-degenerate and the existence of strictly f-degenerate transversals. As consequences, these three classes of graphs are weakly 3-degenerate, and have a strictly f-degenerate transversal. Then these three classes of graph have DP-paint number at most four, and have list vertex arboricity at most two. This greatly improve all the results in [2-4, 11-13, 16-18, 22, 25, 32, 34]. Furthermore, the first and the third classes of graphs have Alon-Tarsi number at most four.