| Title: | Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy |
|---|
| Authors: | ID Kashima, Masaki (Author)
ID Škrekovski, Riste (Author)
ID Xu, Rongxing (Author) |
|---|
| Files: |  URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0012365X26000270
 PDF - Presentation file, download (495,29 KB)
MD5: AD2D3B57BBB88D947CCDB7E69257710D
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  RUDOLFOVO - Rudolfovo - Science and Technology Centre Novo Mesto
|
|---|
| Abstract: | A proper coloring ▫$\phi$▫ 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 ▫$|\phi^{-1}(c) \cap 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)| \ge d_G(v) + k$▫ for every vertex ▫$v \in V(G)$▫, ▫$G$▫ admits a proper conflict-free coloring ▫$\phi$▫ such that ▫$\phi(v) \in L(v)$▫ for every vertex ▫$v \in 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. |
|---|
| Keywords: | proper conflict-free coloring, list coloring, degree-choosability, degeneracy |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.06.2026 |
|---|
| Publisher: | Elsevier |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 5 str. |
|---|
| Numbering: | Vol. 349, iss. 6, [article no.] 115003 |
|---|
| PID: | 20.500.12556/DiRROS-27407  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2026.115003 |
|---|
| COBISS.SI-ID: | 266959619 |
|---|
| Copyright: | © 2026 The Authors |
|---|
| Publication date in DiRROS: | 05.02.2026 |
|---|
| Views: | 44 |
|---|
| Downloads: | 15 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
