The exponential growth of the packing chromatic number of iterated Mycielskians

DOI10.1016/J.DAM.2023.08.007MaRDI QIDQ6069170zbMATH OpenOpenAlexFDO

Authors Ez Zobair Bidine, Taoufiq Gadi, Mustapha Kchikech

Publication date 13 November 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.08.007

iterated Mycielskians maximal triangle-free graphs Mycielskians packing chromatic number packing coloring

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The exponential growth of the packing chromatic number of iterated Mycielskians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6069170)