The color space of a graph
Tommy R. Jensen, Carsten Thomassen · Journal of Graph Theory · 2000
If k is a prime power, and G is a graph with n vertices, then a k-coloring of G may be considered as a vector in \documentclass{article}\usepackage{amssymb}\pagestyle{empty}\begin{document}$\mathbb{GF}$\end{document}(k)n. We prove that the subspace of \documentclass{article}\usepackage{amssymb}\pagestyle{empty}\begin{document}$\mathbb{GF}$\end{document}(3)n spanned by all 3-colorings of a planar triangle-free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3-colorings, and the addition of any edge or any vertex of degree 3 results in a 3-colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000