×

The semi-chromatic number of a graph. (Russian, English) Zbl 1324.05068

Diskretn. Anal. Issled. Oper. 20, No. 1, 3-11 (2013); translation in J. Appl. Ind. Math. 7, No. 2, 269-274 (2013).
Summary: We introduce the notion of the semi-chromatic number of a graph with a nonempty number of edges. Then we prove that the difference between the semi-chromatic number and the half of the chromatic number is at most 1.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI