Premium
The color space of a graph
Author(s) -
Jensen Tommy R.,
Thomassen Carsten
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200007)34:3<234::aid-jgt4>3.0.co;2-g
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , subspace topology , discrete mathematics , mathematical analysis
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