Abstract

A k-subcolouring of a graph G is a function f:V(G)→{0,…,k−1} such that the set of vertices coloured i induce a disjoint union of cliques. The subchromatic number, χsub(G), is the minimum k such that G admits a k-subcolouring. Nešetřil, Ossona de Mendez, Pilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for χsub(G2) when G is planar. We show that χsub(G2)≤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 χsub(G3)≤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 χsub(Gp) for all p≥2, 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 having a layering in which each layer has bounded cliquewidth and this layering is computable in polynomial time (like the class of all dth powers of planar graphs, for fixed d). This algorithm works even if the power p and the graph G is unknown. © 2024 The Author(s)