围长为7的平面图平方图的子色数

Subchromatic Number of the Square of Planar Graphs with Girthat Least 7

摘要: 对于图G, 若被染为同一颜色的顶点所诱导的子图均为若干团的不交井, 则称该染色为子染色, 最 少所需颜色数称为子色数. 图G 的平方图以V(G) 为顶点集, 以原图中距离至多为2 的顶点对为边 集.本文证明了: 对于围长为7 的平面图G, 其平方图的子色数不大于41.证明利用增加边不减小半 弱染色数这一性质, 将原图补充为三角剖分图井构造约化, 再结合围长条件估计各等距路径上的半 弱可达顶点数, 最终得到到所求上界。

Abstract: For a graph G, if the subgraph induced by each color class consists of a disjoint union of cliques, the coloring is called a subcoloring, and the minimum number of colors required is called the subchromatic number. The square of a graph G has vertex set V(G), with two vertices adjacent if and only if their distance in G is at most 2. In this paper, we prove that for every planar graph G of girth at least 7, the subchromatic number of its square is at most 41. The proof exploits the fact that adding edges does not decrease the semi-weak chromatic number. We augment the original graph to a triangulation and construct a reducible configuration argument. Combined with the girth condition, we estimate the number of semi-weakly reachable vertices along isometric paths, thereby establishing the desired upper bound.