2025/09/08 by Masaki Kashima, Kashima, Masaki, Riste Škrekovski +3 · 2 citations
Computer Science · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2509.06280
openalex publication_date 2025/09/08 · openalex created_date 2025/10/10 · 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 to degree-choosability of graphs, the authors recently, in a previous paper, 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 paper, we show that every connected outerplanar graph other than the 5-cycle is proper conflict-free (\rm degree+2)-choosable. This bound is tight in the sense that there are infinitely many connected outerplanar graphs that are not proper conflict-free (\rm degree+1)-choosable. We conclude the paper with two questions for further work.