报告题目：Partition subcubic planar graphs into independent sets

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

报告时间：7月19日  下午4：00-5：00

报告地点：5101

摘要：

A packing $(1^{\ell}, 2^k)$-coloring of a graph $G$ is a partition of $V(G)$ into $\ell$ independent sets and $k$ $2$-packings (whose pairwise vertex distance is at least $3$). The square coloring of planar graphs was first studied by Wegner in 1977. Thomassen and independently Hartke et al. proved that one can always square color a cubic planar graph with $7$ colors, i.e., every subcubic planar graph is packing $(2^7)$-colorable. We focus on packing $(1^{\ell}, 2^k)$-colorings, which lie between proper coloring and square coloring. Gastineau and Togni proved every subcubic graph is packing $(1,2^6)$-colorable and asked whether every subcubic graph except the Petersen graph is packing $(1,2^5)$-colorable.

In this paper, we prove an analogue result of Thomassen and Hartke et al. on packing coloring that every subcubic planar graph is packing $(1,2^5)$-colorable. This also answers the question of Gastineau and Togni affirmatively for subcubic planar graphs. Moreover, we prove that there exists an infinite family of subcubic planar graphs that are not packing $(1,2^4)$-colorable, which shows that our result is the best possible. Besides, our result is also sharp in the sense that the disjoint union of Petersen graphs is subcubic and non-planar, but not packing $(1,2^5)$-colorable. This is a joint work with Yan Wang.