From \(\chi\)- to \(\chi_p\)-bounded classes (Q2099414)

As a refinement of the notion of perfect graphs, a family of graphs \(\mathcal{C}\) is \(\chi\)-bound with binding function \(f\) if \(\chi(H) \le f(\omega(H))\) holds whenever \(G \in \mathcal{C}\) and \(H\) is an induced subgraph of \(G\). Let \(\chi_s(G)\) denote the star chromatic number of a graph \(G\). The notion of \(\chi_s\)-bounded class is considered. \textit{J. Nešetřil} and \textit{P. Ossona de Mendez} [Eur. J. Comb. 27, No. 6, 1022--1041 (2006; Zbl 1089.05025)] introduced a generalization of the chromatic number, which defines a nondecreasing sequence \(\chi_1, \chi_2,\dots\) of graph invariants, where \(\chi_1\) is the usual chromatic number, \(\chi_2\) is the star chromatic number, and \(\chi_p\) is the minimum number of colors of a low tree-depth coloring with parameter \(p\). Motivated by the former studies on bounded expansions, it is defined that a hereditary class \(\mathcal{C}\) is strongly \(\chi_p\)-bounded if, for every \(G \in \mathcal{C}\), we have \(\chi_p \le f_p(\omega(G))\) for some fixed binding function \(f_p\). Weakly \(\chi_p\)-bounded hereditary classes are also introduced in this paper. This paper confirms a former conjecture of \textit{T. Karthick} [Graphs Comb. 34, No. 1, 109--128 (2018; Zbl 1382.05026)] that the class of all \(K_{1,t}\)-free graphs (where \(t \ge 3\)) is \(\chi_s\)-bounded, and disproves another conjecture of Karthick [loc. cit.] on the \(\chi_s\)-boundedness of another class. Furthermore, for any \(p\), characterizations of all strongly \(\chi_p\)-bounded hereditary classes and characterizations of all weakly \(\chi_p\)-bounded hereditary classes are obtained. These characterizations are well done, presenting descriptions of the related \(\chi_p\)-bounded hereditary classes from different angles. The open problems presented in the conclusion section on upper bounding \(\chi_p(G)\) for every graph \(G\) seem quite interesting.