学术报告(刘旭钧 2024.6.28)

Every subcubic graph is packing (1,1,2,2,3)-colorable

发布人:姚璐 发布日期:2024-06-21
主题
Every subcubic graph is packing (1,1,2,2,3)-colorable
活动时间
-
活动地址
新数学楼406
主讲人
刘旭钧 助理教授(西交利物浦大学)
主持人
廖仲行 副教授

Abstract:

For a sequence $S = (s_1, \ldots, s_k)$ of non-decreasing positive integers, a packing $S$-coloring of a graph $G$ is a partition of its vertex set $V(G)$ into $V_1, \ldots, V_k$ such that for every pair of distinct vertices $u,v \in V_i$ the distance between $u$ and $v$ is at least $s_i+1$, where $1 \le i \le k$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is defined to be the smallest integer $k$ such that $G$ has a packing~$(1,2, \ldots, k)$-coloring. Gastineau and Togni asked an open question “Is it true that the $1$-subdivision ($D(G)$) of any subcubic graph $G$ has packing chromatic number at most 5?'” and later Bresar, Klavzar, Rall, and Wash conjectured that it is true. 

In this paper, we prove that every subcubic graph has a packing $(1,1,2,2,3)$-coloring and it is sharp due to the existence of subcubic graphs that are not packing $(1,1,2,2)$-colorable. As a corollary of our result, $\chi_p(D(G)) \le 6$ for every subcubic graph $G$, improving a previous bound (8) due to Balogh, Kostochka, and Liu in 2019, and we are now just one step away from fully solving the conjecture. Joint work with Xin Zhang and Yanting Zhang.