Editing Graph coloring (section)

=== Upper bounds on the chromatic number ===
Assigning distinct colors to distinct vertices always yields a proper coloring, so
: <math>1 \le \chi(G) \le n.</math>

The only graphs that can be 1-colored are [[edgeless graph]]s. A [[complete graph]] <math>K_n</math> of ''n'' vertices requires <math>\chi(K_n)=n</math> colors. In an optimal coloring there must be at least one of the graph's ''m'' edges between every pair of color classes, so
: <math>\chi(G)(\chi(G)-1) \le 2m.</math>

More generally a family <math>\mathcal{F}</math> of graphs is [[Χ-bounded|'''{{math|''χ''}}-bounded''']] if there is some function <math>c</math> such that the graphs <math>G</math> in <math>\mathcal{F}</math> can be colored with at most <math>c(\omega(G))</math> colors, where <math>\omega(G)</math> is the [[clique number]] of <math>G</math>. For the family of the perfect graphs this function is <math>c(\omega(G))=\omega(G)</math>.

The 2-colorable graphs are exactly the [[bipartite graph]]s, including [[tree (graph theory)|tree]]s and forests.
By the four color theorem, every planar graph can be 4-colored.

A [[greedy coloring]] shows that every graph can be colored with one more color than the maximum vertex [[degree (graph theory)|degree]],
: <math>\chi(G) \le \Delta(G) + 1. </math>

Complete graphs have <math>\chi(G)=n</math> and <math>\Delta(G)=n-1</math>,  and [[odd cycle]]s have <math>\chi(G)=3</math> and <math>\Delta(G)=2</math>, so for these graphs this bound is best possible. In all other cases, the bound can be slightly improved; [[Brooks' theorem]]{{sfnp|Brooks|1941}} states that
: '''[[Brooks' theorem]]:''' <math>\chi (G) \le \Delta (G) </math> for a connected, simple graph ''G'', unless ''G'' is a complete graph or an odd cycle.