Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy
Abstract
A proper coloring ϕ of G is called a proper conflict-free coloring of G if for every non-isolated vertex v of G , there is a color c such that | ϕ − 1 ( c ) ∩ N G ( v ) | = 1 . As an analogy of degree-choosability of graphs, we introduced the notion of proper conflict-free ( degree + k ) -choosability of graphs. For a non-negative integer k , a graph G is proper conflict-free ( degree + k ) -choosable if for any list assignment L of G with | L ( v ) | ≥ d G ( v ) + k for every vertex v ∈ V ( G ) , G admits a proper conflict-free coloring ϕ such that ϕ ( v ) ∈ L ( v ) for every vertex v ∈ V ( G ) . In this note, we first remark if a graph G is d -degenerate, then G is proper conflict-free ( degree + d + 1 ) -choosable. Furthermore, when d = 1 , we can reduce the number of colors by showing that every tree is proper conflict-free ( degree + 1 ) -choosable. This motivates us to state a question.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Discrete Mathematics
- Volume
- 349
- Issue
- 6
- Pages
- 115003–115003
- Publication date
- 28 January 2026
- Language
- EN