Title: Packing colorings of subcubic graphs

报告人：刘旭钧 西交利物浦大学

Abstract: For a sequence of non-decreasing positive integers $S = (s_1, \ldots, s_k)$, a packing $S$-coloring is a partition of $V(G)$ into sets $V_1, \ldots, V_k$ such that for each $1\leq i \leq k$ the distance between any two distinct $x,y\in V_i$ is at least $s_i+1$. The smallest $k$ such that $G$ has a packing $(1,2, \ldots, k)$-coloring is called the packing chromatic number of $G$ and is denoted by $\chi_p(G)$. The question whether the packing chromatic number of subcubic graphs is bounded appeared in many papers. Another popular problem in the topic is the conjecture of Bre\v sar, Klav\v zar, Rall and Wash that the packing chromatic number of subdivision of subcubic graphs are bounded above by $5$.

With Balogh and Kostochka, we showed that for every fixed $k$ and $g\geq 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$, which answers the previous question in the negative. In contrast, we proved the first and current best upper bound, $8$, on the conjecture of Bre\v sar et al. We will also talk about recent results which confirm the conjecture of Bre\v sar et al for some subclasses of subcubic graphs.

About the speaker: Liu Xujun, obtained his PhD from Math at UIUC, supervised by Prof. Kostochka. His research interest lies in the field of combinatorics, specifically coloring of graphs, Ramsey theory, and the application of combinatorics in other fields such as information theory and computer science. He currently works at Xi'an Jiaotong-Liverpool University.

时间：2021年11月18日（周四）10:00-11:00

地点：腾讯会议 ID：149 087 730

邀请人：孟宪昌 数学学院教授