Urbana Campus Research Calendar (OVCRI)

Speaker: Zimu Xiang (UIUC)

Title: List coloring $C_3$-free planar graph with a sparse matching of restricted lists

Abstract: A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph, then $G$ has a proper $L$-coloring whenever $|L(x)| = 3$ for $x \in X$ and $|L(v)| = 4$ for $v \in V(G) \setminus X$. As evidence, they proved the conjecture when $G[X]$ is an independent set. We provide further evidence by proving the conjecture when $G[X]$ is an induced sparse matching. This is the first result supporting the conjecture in which the set $X$ receiving smaller lists may induce a non-empty bipartite graph. This is joint work with Stephen Hartke, Yupei Li, Joseph Pappe, Fares Soufan and Lin Tian.