Relaxed coloring of a graph (Q1393026): Difference between revisions

For a family \(\mathcal H\) of graphs, the \(\mathcal H\)-restricted chromatic number of \(G\), \(\chi_{\mathcal H ^ *}(G)\), denotes the minimum \(k\) such that \(G\) admits a partition of the vertices into \(k\) parts, each of which induces a disjoint union of graphs from \(\mathcal H\). When \(\mathcal H = \{K_1\}\), we have \(\chi_{\mathcal H ^ *}(G) = \chi (G)\). Generalizing a well-known result of Erdős about \(\chi\), the authors observe that for any finite \(\mathcal H\) it follows from the result of Erdős that there exist graphs \(G\) of arbitrarily high girth and arbitrary given \(\mathcal H\)-restricted chromatic number of \(G\), \(\chi_{\mathcal H ^ *}(G)\). They proceed to prove, by a probabilistic argument, that these graphs can be chosen so that \(\chi_{\mathcal H ^ *}(G) = \chi (G)\). For a graph \(H\), the \(H\)-forbidden chromatic number of \(G\), \(\chi_{H'}(G)\), is the minimum \(k\) such that \(G\) admits a partition of the vertices into \(k\) parts, each inducing an \(H\)-free subgraph of \(G\). The authors also prove that if \(H\) has girth at least \(g\), then there exist graphs \(G\) of girth at least \(g\) and arbitrarily high \(H\)-forbidden chromatic number of \(G\), \(\chi_{H'}(G)\). Answering earlier questions due to \textit{M. L. Weaver} and \textit{D. B. West} [Graphs Comb. 10, No. 1, 75-93 (1994; Zbl 0796.05036)], they also analyze \(\chi_{\mathcal H ^ *}(G)\) when \(\mathcal H\) consists of a single path and \(G\) is the Cartesian product of odd cycles. Finally they relate versions of these generalized chromatic numbers of lexicographic products to the circular chromatic numbers.