围长至少是8 的平面图G 的平方图的子色数

The Subchromatic Number of the Square Graph of Planar Graph G with Girth at Least 8

摘要: 本文研究的是平面图的平方图的子色数上界问题. 其中: 平面图的平方图是将原平面图中距离不超 过 2 的顶点相连所构成的新图; 图的围长是指图中最短圈的长度; 而子色数的定义与图的特定染色 方式相关. Cortés 等人在 2025 年证明了在平面图围长至少是 3 的一般情形下, 以及围长至少是 10 和 17 时, 其平方图的子色数的上界情况. 本文进一步研究得出了围长至少是 8 的平面图的平方图的子色数的上界为 38.

Abstract: This paper focuses on the problem of the upper bound of the subchromatic number of the square graph of a planar graph. Among these concepts: the square graph of a planar graph is a new graph constructed by connecting vertices in the original planar graph such that the distance between any two connected vertices is no greater than 2; the girth of a graph is defined as the length of its shortest cycle; and the subchromatic number is defined in relation to a particular coloring method of a graph. Cortés et al. proved in 2025 the upper bounds of the subchromatic number of the square graph of a planar graph in the general case where the girth of the planar graph is at least 3, as well as when the girth is 10 and 17. This paper further shows that the upper bound of the subchromatic number of the square graph of a planar graph with girth at least 8 is 38.