The exponential growth of the packing chromatic number of iterated Mycielskians (Q6069170)

A \(k\)-packing coloring of a graph \(G\) with vertex set \(V\), for a given integer \(k\), is a mapping \(f\colon V\rightarrow \{1,\dots,k\}\) such that for any two distinct vertices \(u\) and \(v\), if \(f(u)=f(v)=i\), then \(g_G(u,v)>i\), where \(d_G(u,v)\) is the distance of \(u\) and \(v\) in \(G\). The packing chromatic number \(\chi_{\rho}(G)\) of a graph \(G\) is the smallest integer \(k\) for which \(G\) admits a \(k\)-packing coloring. The decision problem of whether a graph allows a packing coloring with at most \(k\) classes is NP-complete, even for trees (see [\textit{J. Fiala} and \textit{P. A. Golovach}, ibid. 158, No. 7, 771--778 (2010; Zbl 1219.05185)]). Other papers investigated the problem of getting an upper bound of the packing chromatic number by a constant in the class of all cubic graphs. However, \textit{J. Balogh} et al. [Discrete Math. 341, No. 2, 474--483 (2018; Zbl 1376.05047)] proved the existence of cubic graphs with arbitrary large packing chromatic numbers. In general, a trivial upper bound for the packing chromatic number of a graph \(G\) is the following: \[ \chi_{\rho}(G)\le |G|-\alpha(G)+1, \] with equality if \(\operatorname{diam}(G)=2\), where \(|G|\) denotes the order of the graph \(G\) and \(\alpha(G)\) its independence number. Given a graph \(G=(V(G),E(G))\), the Mycielski graph of \(G\), denoted by \(\mu(G)\) and also called Mycielskian of \(G\), is the graph with vertex set \(V(\mu(G))=V(G)\cup V^\prime (G)\cup \{u\}\), where \(V^\prime (G)=\{x^\prime \colon x\in V(G)\}\), and edge set \(E(\mu(G))=E(G)\cup \{xy^\prime \colon xy\in E(G)\}\cup \{y^\prime u\colon y^\prime \in V^\prime (G)\}\). The \(t\)-iterated Mycielskian of \(G\), denoted by \(\mu^t(G)\), is the transformation of \(G\) defined by \(\mu^0(G)=G\) and \(\mu^t(G)=\mu(\mu^{t-1}(G)))\) for \(t\ge 1\). Note that if \(G\) is triangle-free, then \(\mu^t(G)\) is also triangle-free. A triangle-free graph is maximal triangle-free (MTF) if no edge can be added without producing a triangle. Given a graph \(G\) and \(A\subset V(G)\), let \(G[X]\) denote the subgraph of \(G\) induced by the vertices of \(A\). \textit{J. Balogh} et al. [Forum Math. Sigma 3, Paper No. e20, 19 p. (2015; Zbl 1323.05073)] proved the following: Theorem 1. For almost every maximal triangle-free graph \(G\) of order \(n\), there is a vertex partition \(X\cup Y\) such that \(G[X]\) is a perfect matching and \(Y\) is an independent set. MTF graphs whose vertex set can be partitioned into \(X\cup Y\) such that \(G[X]\) is a perfect matching and \(Y\) is an independent set are called MTF graphs with typical structure. In this paper, the authors investigate graphs for which \(\chi_{\rho}(\mu^t(G))=2^t\chi_{\rho}(G)\). Precisely, they consider the set \(\mathcal P\) of graphs whose vertex set can be partitioned into \(X\cup Y\) where \(Y\) is an independent set, \(|X|<|Y|\) and there exists an \(|X|\)-matching \(M\) such that \(M=\{xy\colon x\in X,\, y\in Y\}\). In this paper the following result is proved: Theorem 2. For every connected graph \(G\) and every \(t\ge 1\), \[ \chi_{\rho}(\mu^t(G))\le 2^t(|G|-\alpha(G)+1). \] If \(G\) has diameter \(2\), a better upper bound is given by: Theorem 3. For all \(t\ge 1\), if \(G\) is a graph of diameter \(2\), then for all \(t\ge 1\), \[ \chi_{\rho}(\mu^t(G))\le 2^t\chi_{\rho}(G), \] with equality if \(G\in \mathcal P\). Now, the authors consider the problem of whether all iterated Mycielskians of the graph \(G\) have a packing chromatic number that grows exponentially in terms of that of \(G\). So, they study graphs for which the equality \(\chi_{\rho}(\mu^t(G))= 2^t\chi_{\rho}(G)\) holds. MTF graphs are good candidates because they have diameter two, but generally, MTF graphs are not in \(\mathcal P\). So, at last, the authors in this paper propose a graph transformation that allows to construct a family of MTF graphs \((T_n)_{n\ge 5}\) with a typical structure such that \(T_n\in\mathcal P\) for all \(n\ge 5\), so that for this family of graphs the equality \(\chi_{\rho}(\mu^t(G))= 2^t\chi_{\rho}(G)\) holds.