报告时间： 2025年11月14日（周五）下午14:30-15:30

报告地点：苏州大学本部精正楼306

报告人：刘旭钧（Assistant Professor），西交利物浦大学

摘要：

An i-independent set is a set of vertices whose pairwise distance is at least i+1. A proper coloring (resp. a square coloring) of a graph is a partition of its vertices into independent (resp. 2-independent) sets. A packing (1^j, 2^k)-coloring of a graph is a partition of its vertices into j independent sets and k 2-independent sets; this is an intermediate coloring between proper coloring and square coloring. We investigate classes of sparse graphs that have a proper (j+1)-coloring but no packing (1^j, 2^k)-coloring for any finite k.

The Four-Color Theorem states that every planar graph is packing (1^4)-colorable, and Grötzsch's Theorem says every planar graph with girth at least 4 is packing (1^3)-colorable.

However, for every fixed k, we construct a planar graph with no packing (1^3, 2^k)-coloring and a planar graph with girth 6 that has no packing (1^2, 2^k)-coloring. Moreover, for every positive integer j, we completely determine the minimum girth condition g(j) for which every planar graph with girth at least g(j) has a packing (1^j, 2^{f(j)})-coloring for some finite f(j). Our results are actually in terms of maximum average degree.

This is based on a joint work with Ilkyoo Choi.

邀请人：汪馨