Inequalities between the domination number and the chromatic number of a graph (Q1121277)

The following inequalities between the domination number \(\sigma\) and the chromatic number \(\chi\) of a (simple) graph on p vertices are proved by a direct application and combination of several old and newer results on these parameters: For all graphs G it holds \(\sigma +\chi \leq p+1\) with equality if and only if \(G\cong K_ p.\) For all connected graphs G with \(p\geq 5\) it holds \(\sigma\) \(\chi\leq \frac{p^ 2}{4}\) with equality if and only if G consists of a \(K_{p/2}\) (p even) each of whose vertices is connected with an endvertex. For all regular graphs with \(p\geq 5\) it holds \(\sigma\) \(\chi\leq \frac{6}{25}p^ 2\) with equality if and only if \(G\cong C_ 5\).