# 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
##### Keywords:
chromatic number; connected graph
Full Text: