Talk information

Date: Sunday, July 21, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Danny Hefetz (Ariel University)
Title: Colouring graphs from random lists

Abstract:

Given positive integers $k \leq m$ and a graph $G$, a family of lists $\mathcal{L} = \{L(v) : v \in V(G)\}$ is said to be a random $(k,m)$-list-assignment if for every $v \in V(G)$ the list $L(v)$ is a subset of $\{1, \ldots, m\}$ of size $k$, chosen uniformly at random and independently of the choices of all other vertices. An $n$-vertex graph $G$ is said to be a.a.s. $(k,m)$-colourable if $\lim_{n \to \infty} \mathbb{P}(G \textrm{ is } \mathcal{L}\textrm{-colourable}) = 1$, where $\mathcal{L}$ is a random $(k,m)$-list-assignment. We prove that if $m \gg n^{1/k^2} \Delta^{1/k}$ and $m \geq 3 k^2 \Delta$, where $\Delta$ is the maximum degree of $G$ and $k \geq 3$ is an integer, then $G$ is a.a.s. $(k,m)$-colourable. This is not far from being best possible, forms a continuation of the so-called palette sparsification results, and proves in a strong sense a conjecture of Casselgren. Additionally, we consider this problem under the additional assumption that $G$ is $H$-free for some graph $H$. For various graphs $H$, we estimate the smallest $m_0$ for which any $H$-free $n$-vertex graph $G$ is a.a.s. $(k,m)$-colourable for every $m \geq m_0$. This extends and improves several results of Casselgren.

Based on joint work with Michael Krivelevich