Generalizations of independence and chromatic numbers of a graph (Q1801703)

This paper adds one more generalization of graph-coloring to the many already in the literature (see \textit{J. I. Brown} and \textit{D. G. Corneil} [On generalized graph colorings, J. Graph Theory 11, 87-99 (1987; Zbl 0608.05035)], for example). Given a graph \(G\) and an integer \(k\geq 2\), a set \(S\) of vertices of \(G\) is \(k\)-independent (an \(I_ k\)-set) if the subgraph induced by any \(k\)-point subset of \(S\) is disconnected (for \(k=2\) this becomes the standard definition of independence). This generalization leads to the definition of the \(k\)-independence number of \(G\) as the maximum cardinality of an \(I_ k\)-set, an \(I_ k\)-coloring of \(G\) as a coloring of the vertices of \(G\) such that the set of all vertices receiving the same color is an \(I_ k\)-set, and the \(k\)- chromatic number \(\chi_ k(G)\) of \(G\) as the minimum number of colors needed in an \(I_ k\)-coloring of \(G\). Among other generalizations of known results about independence numbers and chromatic numbers to their \(k\)-analogues, it is shown that for any positive integer \(n\) there is a \(K_{k+1}\)-free graph \(G\) with \(\chi_ k(G)=n\). A graph \(G\) with \(\chi_ k(G)=n\) is called \((k,n)\)-critical (resp., \((k,n)\)-minimal) if removing any vertex (resp. edge) reduces the \(k\)- chromatic number. Some results about \(n\)-critical and \(n\)-minimal graphs are generalized to their \(k\)-analogues including a characterization in \textit{B. Toft} [On critical subgraphs of color-critical graphs, Discrete Math. 7, 377-392 (1974; Zbl 0271.05112)] of \(n\)-critical graphs in terms of their \((n-1)\)-critical subgraphs.