Note on \(k\)-chromatic graphs. (English) Zbl 0805.05028

Marcu, Dănuţ

Math. Bohem. 119, No. 1, 43-48 (1994).

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)\).

Reviewer: J.Fiamčik (Prešov)

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

chromatic number; connected graph