×

zbMATH — the first resource for mathematics

Note on \(k\)-chromatic graphs. (English) Zbl 0805.05028
The author considers graphs with chromatic number \(k\) and order \(n\), and he proves that (i) any graph without isolated vertices has size at least \({k \choose 2} + \lceil (n - k)/2 \rceil\), and (ii) the minimal number of edges of a connected graph is equal to \({k \choose 2} + n - k\) \((2 \leq k \leq n)\).
MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: EuDML