Title: Subchromatic numbers of powers of graphs with excluded minors Show Chinese title

Title: 图的幂的子色数与排除小图的条件

Abstract: A $k$-subcolouring of a graph $G$ is a function $f:V(G) \to \{0,\ldots,k-1\}$ such that the set of vertices coloured $i$ induce a disjoint union of cliques. The subchromatic number, $\chi_{\textrm{sub}}(G)$, is the minimum $k$ such that $G$ admits a $k$-subcolouring. Ne\v{s}et\v{r}il, Ossona de Mendez, Pilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for $\chi_{\textrm{sub}}(G^2)$ when $G$ is planar. We show that $\chi_{\textrm{sub}}(G^2)\le 43$ when $G$ is planar, improving their bound of 135. We give even better bounds when the planar graph $G$ has larger girth. Moreover, we show that $\chi_{\textrm{sub}}(G^{3})\le 95$, improving the previous bound of 364. For these we adapt some recent techniques of Almulhim and Kierstead (2022), while also extending the decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez, Quiroz, Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that these decompositions are the precursors of the graph product structure theorem of planar graphs. We give improved bounds for $\chi_{\textrm{sub}}(G^p)$ for all $p$, whenever $G$ has bounded treewidth, bounded simple treewidth, bounded genus, or excludes a clique or biclique as a minor. For this we introduce a family of parameters which form a gradation between the strong and the weak colouring numbers. We give upper bounds for these parameters for graphs coming from such classes. Finally, we give a 2-approximation algorithm for the subchromatic number of graphs coming from any fixed class with bounded layered cliquewidth. In particular, this implies a 2-approximation algorithm for the subchromatic number of powers $G^p$ of graphs coming from any fixed class with bounded layered treewidth (such as the class of planar graphs). This algorithm works even if the power $p$ and the graph $G$ is unknown. Show Chinese abstract

Abstract: 一个$k$-子着色的图$G$是一个函数$f:V(G) \to \{0,\ldots,k-1\}$，使得着色为$i$的顶点集诱导出团的不相交并。 子着色数，$\chi_{\textrm{sub}}(G)$，是使得$G$允许$k$-子着色的最小$k$。Nešetřil, Ossona de Mendez, Pilipczuk和Zhu（2020）最近提出了寻找当$G$为平面时$\chi_{\textrm{sub}}(G^2)$的紧上界的問題。 我们证明了当$G$为平面图时，$\chi_{\textrm{sub}}(G^2)\le 43$，改进了他们对135的界限。当平面图$G$具有更大的围长时，我们给出了更好的界限。此外，我们证明了$\chi_{\textrm{sub}}(G^{3})\le 95$，改进了之前的364的界限。为了这些结果，我们采用了 Almulhim 和 Kierstead（2022）的一些最近技术，同时还将 Van den Heuvel、Ossona de Mendez、Quiroz、Rabinovich 和 Siebertz（2017）对三角形平面图的分解扩展到任意围长的平面图。请注意，这些分解是平面图的图积结构定理的前身。我们给出了当$G$具有有界树宽、有界简单树宽、有界亏格或排除一个团或双团作为子式时，$\chi_{\textrm{sub}}(G^p)$对所有$p$的改进界限。为此，我们引入了一类参数，这些参数在强着色数和弱着色数之间形成一种渐变。我们给出了来自此类图的这些参数的上界。最后，我们给出了一个2-近似算法，用于任何固定类中具有有界层状团宽的图的次色数。 特别是，这表明对于来自任何具有有界分层树宽的图类（如平面图类）的幂图$G^p$的子色数，存在一个2-近似算法。该算法甚至在幂图$p$和图$G$未知的情况下仍然有效。