Asymptotically Optimal Proper Conflict-Free Colouring

Fuente: arXiv
Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Liu, Chun-Hung, Reed, Bruce
Format: Preprint
Veröffentlicht: 2024
Schlagworte:
Online-Zugang:
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
_version_ 1866915266012643328
author Liu, Chun-Hung
Reed, Bruce
author_facet Liu, Chun-Hung
Reed, Bruce
contents A proper conflict-free colouring of a graph is a colouring of the vertices such that any two adjacent vertices receive different colours, and for every non-isolated vertex $v$, some colour appears exactly once on the neighbourhood of $v$. Caro, Petruševski and Škrekovski conjectured that every connected graph with maximum degree $Δ\geq 3$ has a proper conflict-free colouring with at most $Δ+1$ colours. This conjecture holds for $Δ=3$ and remains open for $Δ\geq 4$. In this paper we prove that this conjecture holds asymptotically; namely, every graph with maximum degree $Δ$ has a proper conflict-free colouring with $(1+o(1))Δ$ colours.
format Preprint
id arxiv_https___arxiv_org_abs_2401_02155
institution arXiv
publishDate 2024
record_format arxiv
spellingShingle Asymptotically Optimal Proper Conflict-Free Colouring
Liu, Chun-Hung
Reed, Bruce
Combinatorics
A proper conflict-free colouring of a graph is a colouring of the vertices such that any two adjacent vertices receive different colours, and for every non-isolated vertex $v$, some colour appears exactly once on the neighbourhood of $v$. Caro, Petruševski and Škrekovski conjectured that every connected graph with maximum degree $Δ\geq 3$ has a proper conflict-free colouring with at most $Δ+1$ colours. This conjecture holds for $Δ=3$ and remains open for $Δ\geq 4$. In this paper we prove that this conjecture holds asymptotically; namely, every graph with maximum degree $Δ$ has a proper conflict-free colouring with $(1+o(1))Δ$ colours.
title Asymptotically Optimal Proper Conflict-Free Colouring
topic Combinatorics
url https://arxiv.org/abs/2401.02155