Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy
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.
Authors
- Masaki Kashima (ORCID: https://orcid.org/0009-0006-8710-169X)
- Rongxing Xu (ORCID: https://orcid.org/0009-0005-1809-1179)
- Riste Škrekovski
Institutions
- Zhejiang Normal University (CN)
- Keio University (JP)
- Higher Education Centre Novo Mesto (SI)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2026-01-28
- DOI
- https://doi.org/10.1016/j.disc.2026.115003
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00