Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy

Read full text
Authors: Masaki Kashima, Riste Škrekovski, Rongxing Xu
Cited by: 0
References: 8

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