Bounds on the \(k\)-Independence and \(k\)-Chromatic Numbers of Graphs.

Abstract

For an integer \(k \geq 1\) and a graph \(G = (V, E)\), a subset \(S\) of the vertex set \(V\) is \(k\)-independent in \(G\) if the maximum degree of the subgraph induced by the vertices of \(S\) is less than or equal to \(k – 1\). The \(k\)-independence number \(\beta_k(G)\) of \(G\) is the maximum cardinality of a \(k\)-independent set of \(G\). A set \(S\) of \(V\) is \(k\)-Co-independent in \(G\) if \(S\) is \(k\)-independent in the complement of \(G\). The \(k\)-Co-independence number \(\omega_k(G)\) of \(G\) is the maximum size of a \(k\)-Co-independent set in \(G\). The sequences \((\beta_k)\) and \((\omega_k)\) are weakly increasing. We define the \(k\)-chromatic number or \(k\)-independence partition number \(\chi_k(G)\) of \(G\) as the smallest integer \(m\) such that \(G\) admits a partition of its vertices into \(m\) \(k\)-independent sets and the \(k\)-Co-independence partition number \(\theta_k(G)\) of \(G\) as the smallest integer \(m\) such that \(G\) admits a partition of its vertices into \(m\) \(k\)-Co-independent sets. The sequences \((\chi_k)\) and \((\theta_k)\) are weakly decreasing. In this paper, we mainly present bounds on these four parameters, some of which are extensions of well-known classical results.