2025/09/16 by Masaki Kashima, Kashima, Masaki, Riste Škrekovski +3 · 1 citation
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2509.12560
openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
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)∩ NG(v)|=1. As an analogy of degree-choosability of graphs, we introduced the notion of proper conflict-free (\rm degree+k)-choosability of graphs. For a non-negative integer k, a graph G is proper conflict-free (\rm degree+k)-choosable if for any list assignment L of G with |L(v)|≥ dG(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 (\rm degree+d+1)-choosable. Furthermore, when d=1, we can reduce the number of colors by showing that every tree is proper conflict-free (\rm degree+1)-choosable. This motivates us to state a question.