Editing Graph coloring (section)

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