Editing Graph coloring (section)

=== Open problems ===
As stated above, <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> A conjecture of Reed from 1998 is that the value is essentially closer to the lower bound, 
<math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math>

The [[Hadwiger–Nelson problem|chromatic number of the plane]], where two points are adjacent if they have unit distance, is unknown, although it is one of 5, 6, or 7. Other [[unsolved problems in mathematics|open problems]] concerning the chromatic number of graphs include the [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] stating that every graph with chromatic number ''k'' has a [[complete graph]] on ''k'' vertices as a [[graph minor|minor]], the [[Erdős–Faber–Lovász conjecture]] bounding the chromatic number of unions of complete graphs that have at most one vertex in common to each pair, and the [[Albertson conjecture]] that among ''k''-chromatic graphs the complete graphs are the ones with smallest [[crossing number (graph theory)|crossing number]].

When Birkhoff and Lewis introduced the chromatic polynomial in their attack on the four-color theorem, they conjectured that for planar graphs ''G'', the polynomial <math>P(G,t)</math> has no zeros in the region <math>[4,\infty)</math>. Although it is known that such a chromatic polynomial has no zeros in the region <math>[5,\infty)</math> and that <math>P(G,4) \neq 0</math>, their conjecture is still unresolved. It also remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine which polynomials are chromatic.