Editing Graph coloring (section)

== Properties ==

=== 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.

=== Lower bounds on the chromatic number ===
Several lower bounds for the chromatic bounds have been discovered over the years:

If ''G'' contains a [[clique (graph theory)|clique]] of size ''k'', then at least ''k'' colors are needed to color that clique; in other words, the chromatic number is at least the clique number:
: <math>\chi(G) \ge \omega(G).</math>

For [[perfect graph]]s this bound is tight. Finding cliques is known as the [[clique problem]].

'''Hoffman's bound:''' Let <math>W</math> be a real symmetric matrix such that <math> W_{i,j} = 0 </math> whenever <math>(i,j) </math> is not an edge in <math>G</math>. Define <math>\chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}</math>, where <math>\lambda_{\max}(W), \lambda_{\min}(W)</math> are the largest and smallest eigenvalues of <math>W</math>. Define <math display="inline"> \chi_H(G) = \max_W \chi_W(G)</math>, with <math>W</math> as above. Then:
: <math> \chi_H(G)\leq \chi(G).</math>

'''{{vanchor|Vector chromatic number}}:''' Let <math>W</math> be a positive semi-definite matrix such that <math> W_{i,j} \le -\tfrac{1}{k-1} </math> whenever <math>(i,j) </math> is an edge in <math>G</math>. Define <math>\chi_V(G)</math> to be the least k for which such a matrix <math>W</math> exists. Then
: <math> \chi_V(G)\leq \chi(G).</math>

'''[[Lovász number]]:''' The Lovász number of a complementary graph is also a lower bound on the chromatic number:
: <math> \vartheta(\bar{G}) \leq \chi(G).</math>

'''[[Fractional chromatic number]]:''' The fractional chromatic number of a graph is a lower bound on the chromatic number as well:
: <math> \chi_f(G) \leq \chi(G).</math>

These bounds are ordered as follows:
: <math> \chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G).</math>

=== Graphs with high chromatic number ===
Graphs with large [[Clique (graph theory)|cliques]] have a high chromatic number, but the opposite is not true. The [[Grötzsch graph]] is an example of a 4-chromatic graph without a triangle, and the example can be generalized to the [[Mycielskian]]s.
: '''Theorem''' ({{harvard citations|nb|first=William T.|last=Tutte|year=1947|author-link=W. T. Tutte}},{{sfnp|Descartes|1947}} {{harvard citations|nb|first=Alexander|last=Zykov|year=1949|author-link=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|author-link=Jan Mycielski}}): There exist triangle-free graphs with arbitrarily high chromatic number.

To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of [[triangle-free graph]]s but with arbitrarily large chromatic number.{{sfnp|Scott|Seymour|2020}} {{harvtxt|Burling|1965}} constructed axis aligned boxes in <math>\mathbb{R}^{3}</math> whose [[intersection graph]] is triangle-free and requires arbitrarily many colors to be properly colored. This family of graphs is then called the Burling graphs. The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al. (2014).{{sfnp|Pawlik|Kozik|Krawczyk|Lasoń|2014}} It shows that the chromatic number of its intersection graph is arbitrarily large as well. Hence, this implies that axis aligned boxes in <math>\mathbb{R}^{3}</math> as well as line segments in <math>\mathbb{R}^{2}</math> are not [[χ-bounded|''χ''-bounded]].{{sfnp|Pawlik|Kozik|Krawczyk|Lasoń|2014}}

From Brooks's theorem, graphs with high chromatic number must have high maximum degree. But colorability is not an entirely local phenomenon: A graph with high [[Girth (graph theory)|girth]] looks locally like a tree, because all cycles are long, but its chromatic number need not be 2:
: '''Theorem''' ([[Paul Erdős|Erdős]]): There exist graphs of arbitrarily high girth and chromatic number.{{sfnp|Erdős|1959}}

=== Bounds on the chromatic index ===
An edge coloring of ''G'' is a vertex coloring of its [[line graph]] <math>L(G)</math>, and vice versa. Thus,
: <math>\chi'(G)=\chi(L(G)). </math>

There is a strong relationship between edge colorability and the graph's maximum degree <math>\Delta(G)</math>. Since all edges incident to the same vertex need their own color, we have
: <math>\chi'(G) \ge \Delta(G).</math>

Moreover,
: '''[[Kőnig's theorem (graph theory)|Kőnig's theorem]]:''' <math>\chi'(G) = \Delta(G)</math> if ''G'' is bipartite.

In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring:
: '''[[Vizing's theorem|Vizing's Theorem:]]''' A graph of maximal degree <math>\Delta</math> has edge-chromatic number <math>\Delta</math> or <math>\Delta+1</math>.

=== Other properties ===
A graph has a ''k''-coloring if and only if it has an [[acyclic orientation]] for which the [[longest path]] has length at most ''k''; this is the [[Gallai–Hasse–Roy–Vitaver theorem]] {{harv|Nešetřil|Ossona de Mendez|2012}}.

For planar graphs, vertex colorings are essentially dual to [[nowhere-zero flows]].

About infinite graphs, much less is known.
The following are two of the few results about infinite graph coloring:
*If all finite subgraphs of an [[infinite graph]] ''G'' are ''k''-colorable, then so is ''G'', under the assumption of the [[axiom of choice]]. This is the [[De Bruijn–Erdős theorem (graph theory)|de Bruijn–Erdős theorem]] of {{harvtxt|de Bruijn|Erdős|1951}}.
*If a graph admits a full ''n''-coloring for every ''n'' ≥ ''n''<sub>0</sub>, it admits an infinite full coloring {{harv|Fawcett|1978}}.

=== 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.