Chromatic partitions of a graph (Q1263595)

The chromatic partition number \(\chi_ k(G)\) (k\(\geq 1)\) of a graph G is defined to be the minimum number of colours needed in a \(P_ k\)- colouring of G. The following are the main results: (1) For any graph G of order p, \[ \frac{p}{M_ k}\leq \chi_ k(G)\leq \{\frac{p-M_ k}{k}\}+1\quad and\quad -\frac{p}{\beta_ 0k}\leq \chi_ k(G)\leq \{\frac{p-\beta_ k}{k}\}+1, \] where \(M_ k\) is the maximum number of points in a \(P_ k\)-set of G, \(\beta_ 0\) is the independence number of G and \(\{\) \(r\}\) is the least integer not less than r. (2) For any positive integer n, there exists a \(K_{k+2}\)-free graph G with \(\chi_ k(G)=n.\) (3) For \(n\geq 2\), every (k,n)-critical graph is \(n+(k-2)\)-line connected. (4) For any graph G with \(\chi_ k(G)\pm n\geq 2\), \(\chi_ k(G)\leq \max \delta (G^ 1)-k+2\), where the max is taken over all induced subgraphs \(G^ 1\) of G. (5) For any graph G and for any integer \(k\geq 1\), \(\chi_ k(G)\leq 1+[\frac{m(G)}{k}]\), where m(G) is the largest eigenvalue of the adjacency matrix of G.