| Naslov: | Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy |
|---|
| Avtorji: | ID Kashima, Masaki (Avtor)
ID Škrekovski, Riste (Avtor)
ID Xu, Rongxing (Avtor) |
|---|
| Datoteke: |  URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0012365X26000270
 PDF - Predstavitvena datoteka, prenos (495,29 KB)
MD5: AD2D3B57BBB88D947CCDB7E69257710D
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  RUDOLFOVO - Rudolfovo – Znanstveno in tehnološko središče Novo mesto
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | proper conflict-free coloring, list coloring, degree-choosability, degeneracy |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.06.2026 |
|---|
| Založnik: | Elsevier |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 5 str. |
|---|
| Številčenje: | Vol. 349, iss. 6, [article no.] 115003 |
|---|
| PID: | 20.500.12556/DiRROS-27407  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2026.115003 |
|---|
| COBISS.SI-ID: | 266959619 |
|---|
| Avtorske pravice: | © 2026 The Authors |
|---|
| Datum objave v DiRROS: | 05.02.2026 |
|---|
| Število ogledov: | 42 |
|---|
| Število prenosov: | 13 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
