报告题目：The square of every subcubic planar graph of girth at least 6 is 7-choosable
报告人：Seog-Jin Kim教授，韩国建国大学
报告时间：2023年7月31日，14:00-15:00（北京时间）
报告地点：腾讯会议，692-956-121
摘要：
The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner's conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) = 3$,at most $\Delta(G)+5$ if $4 \leq \Delta(G) \leq 7$, and at most $\lfloor \frac{3 \Delta(G)}{2} \rfloor$ if $\Delta(G) \geq 8$.Wegner's conjecture is still wide open. The only case for which we know tight bound is when $\Delta(G) = 3$. Thomassen (2018) showed that $\chi(G^2) \leq 7$ if $G$ is a planar graph with $\Delta(G) = 3$, which implies that Wegner's conjecture is true for $\Delta(G) = 3$.A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph,where $\chi_{\ell}(G^2)$ is the list chromatic number of $G^2$.Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if$G$ is a subcubic planar graph of girth at least 6. This is joint work with Xiaopan Lian (Nankai University).
邀请人：朱绪鼎